Circuitos e conjuntos de números naturais

Circuitos sobre 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 grafos acíclicos dirigidos 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]