Circuitos sobre conjuntos de números naturais

Circuitos sobre conjuntos de números naturais são um modelo matemático utilizado no estudo da teoria da complexidade computacional. Eles são um caso especial de circuitos. O objeto é classificado como grafo acíclicos dirigidos a nós do que avaliar os conjuntos dos números naturais, as folhas são conjuntos finitos, e as portas são operações de conjuntos ou operações aritméticas.

Como um problema algorítmico, o problema é descobrir se um dado número natural é um elemento do nó de saída ou se dois circuitos calculam o mesmo conjunto. Decidibilidade é ainda uma questão em aberto.

Definição Formal

Um circuito de número natural é um circuito, isto é, um grafo acíclico dirigido classificado de grau 2 no máximo. Os nós de grau 0, as folhas, são finitos conjuntos de números naturais, as classificações dos nós de grau 1 são −, onde e as classificações dos nós de grau 2 são de +, ×, ∪ e ∩, onde , e ∪ e ∩ com o habitual conjunto de significado.

O subconjunto de circuitos que não usam todos as possível classificações são também estudados.

Problemas algorítmicos

Pode-se perguntar:

É dado número n de um membro do nó de saída.
É o nó de saída vazio, não contêm um elemento específico, é igual a ?
Um nó é um subconjunto do outro.

Para circuitos que usam todas as classificações, todos esse problemas são equivalentes.

Prova

O primeiro problema é redutível ao segundo, tomando o ponto de intersecção do porta de saída e a de n. De fato, a nova saída estará vazio se e somente se n não era um elemento da porta de saída anterior.

O primeiro problema é redutível ao terceiro, perguntando se o nó n é um subconjunto do nó de saída.

O segundo problema é redutível ao primeiro, basta multiplicar a porta de saída por 0, 0 vai ser na saída da porta se, e somente se, a antiga porta de saída não estava vazia.

O terceiro problema é redutível ao segundo, verificando se A é um subconjunto de B é equivalente a perguntar se existe um elemento em .

Restrições

Deixe O ser um subconjunto de {∪,∩,−,+,×}, então chamamos MC(O) o problema de se encontrar um número natural é dentro da porta de saída de um circuito de portas' descrições dos que estão em O e MF(O) o mesmo problema com a restrição de que o circuito deve ser uma árvore.

Crescimento rápido de conjunto

Uma dificuldade vem do fato de que o complemento de um conjunto finito é infinita, e um computador tem apenas uma memória finita. Mas, mesmo sem a complementação, pode-se criar uma função exponencial dupla de números. Deixe e , em seguida, pode-se facilmente provar por indução em que , de fato, e por indução .

E mesmo uma função exponencial dupla—tamanho de conjunto: deixe $S_{0}=\{0,1,2\},S_{i+1}=(S_{i}\times S_{i})+S_{i}$ , em seguida $\{x|0<x<2^{2^{i}}\}\subset S_{i}$ , isto é $S_{i}$ contém $2^{2^{i}}$ primeiros números. Mais uma vez isso pode ser provado por indução sobre $i$ ,isso é verdade para $S_{0}$ por definição e deixe $x\in \{x|0<x<2^{2^{i+1}}\}$ , dividindo $x$ por $2^{2^{i}}$ nós vemos que pode ser escrito como $x=2^{2^{i}}\times d+r$ onde $d,r<2^{2^{i}}$ , e por indução, $2^{2^{i}},d$ e $r$ estão dentro de $S_{i}$ , assim certamente $x\in (S_{i}\times S_{i})+S_{i}$ .

Estes exemplos explicam por que a adição e a multiplicação são o suficiente para criar problemas de alta complexidade.

Resultados de complexidade

A associação problema

O problema de associação pede-se, dado um elemento n e um circuito, n é a porta de saída do circuito.

Quando a classe de portas autorizadas é restrita , o problema de adesão está dentro classes de complexidade bem conhecidas.

Complexidade
O	MC(O)	MF(O)
∪,∩,−,+,×	NEXPTIME-difícil Decidíveis com uma máquina oráculo para o problema da parada	PSPACE-difícil
∪,∩,+,×	NEXPTIME-completo	NP-completo
∪,+,×	PSPACE-completo	NP-completo
∩,+,×	P-difícil, em co-R	LOGCFL
+,×	P-completo	L-completo
∪,∩,−,+	PSPACE-completo	PSPACE-completo
∪,∩,+	PSPACE-completo	NP-completo
∪,+	NP-completo	NP-completo
∩,+	C₌L-completo	L-completo
+	C₌L-completo	L-completo
∪,∩,−,×	PSPACE-completo	PSPACE-completo
∪,∩,×	PSPACE-completo	NP-completo
∪,×	NP-completo	NP-completo
∩,×	C₌L-difícil, em P	L-completo
×	NL-completo	L-completo
∪,∩,−	P-completo	NC¹-completo
∪,∩	P-completo	L-completo
∪	NL-completo	L-completo
∩	NL-completo	L-completo

Problema de equivalência

A equivalência problema pergunta se, dadas duas portas de um circuito, elas avaliam para o mesmo conjunto.

Quando a classe de portas autorizadas é restrita , o problema de equivalência está dentro classes de complexidade bem conhecidas .^[1] Chamamos EC(O) e EF(O) o problema de equivalência através de circuitos e fórmulas das portas que estão em O.

Complexidade
O	EC(O)	EF(O)
∪,∩,−,+,×	NEXPTIME-difícil Decidíveis com uma máquina oráculo para o problema da parada	PSPACE-difícil Decidíveis com uma máquina oráculo para o problema da parada
∪,∩,+,×	NEXPTIME-difícil, em coNEXP^NP	Π^P₂-completo
∪,+,×	NEXPTIME-difícil, em coNEXP^NP	Π^P₂-completo
∩,+,×	P-difícil, em BPP	L-difícil, em LOGCFL
+,×	L-difícil, em LOGCFL	P-difícil, em coRP
∪,∩,−,+	PSPACE-completo	PSPACE-completo
∪,∩,+	PSPACE-completo	Π^P₂-completo
∪,+	Π^P₂-completo	Π^P₂-completo
∩,+	coC₌L(2)-completo	L-completo
+	C₌L-completo	L-completo
∪,∩,−,×	PSPACE-completo	PSPACE-completo
∪,∩,×	PSPACE-completo	Π^P₂-completo
∪,×	Π^P₂-completo	Π^P₂-completo
∩,×	coC₌L(2)-difícil, em P	L-completo
×	C₌L-difícil, em P	L-completo
∪,∩,−	P-completo	L-completo
∪,∩	P-completo	L-completo
∪	NL-completo	L-completo
∩	NL-completo	L-completo

Referências

↑ Christian Glaßer; Katrin Herr; Christian Reitwießner; Stephen Travers; Matthias Waldherr (2007), «Equivalence Problems for Circuits over Sets of Natural Numbers», ISBN 978-3-540-74509-9 (what is called "number" in bibtex) ed. , Berlin / Heidelberg: Springer, Lecture Notes in Computer Science, Volume 4649/2007: 127–138, doi:10.1007/978-3-540-74510-5

Travers, Stephen (2006), The Complexity of Membership Problems for Circuits over Sets of Natural Numbers, Theoretical Computer Science, ISSN 0304-3975, 389 (1), pp. 211–229

Pierre McKenzie; Klaus W. Wagner (2003), «The Complexity of Membership Problems for Circuits over Sets of Natural Numbers», ISBN 3-540-00623-0, Springer-Verlag, Lecture Notes In Computer Science, 2607: 571–582

Ligações externas

Pierre McKenzie, A complexidade do circuito de avaliação sobre os números naturais

[1] Christian Glaßer; Katrin Herr; Christian Reitwießner; Stephen Travers; Matthias Waldherr (2007), «Equivalence Problems for Circuits over Sets of Natural Numbers», ISBN 978-3-540-74509-9 (what is called "number" in bibtex) ed. , Berlin / Heidelberg: Springer, Lecture Notes in Computer Science, Volume 4649/2007: 127–138, doi:10.1007/978-3-540-74510-5

[1]