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 ${\displaystyle }$ e as classificações dos nós de grau 2 são de +, ×, ∪ e ∩, onde ${\displaystyle }$, ${\displaystyle }$ 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 ${\displaystyle }$?
• 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 ${\displaystyle }$.

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 ${\displaystyle }$e , em seguida, pode-se facilmente provar por indução em ${\displaystyle }$ que ${\displaystyle }$ , de fato, ${\displaystyle }$ e por indução ${\displaystyle }$.

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	NC1-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 . 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 coNEXPNP	ΠP2-completo
∪,+,×	NEXPTIME-difícil, em coNEXPNP	ΠP2-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	ΠP2-completo
∪,+	ΠP2-completo	ΠP2-completo
∩,+	coC=L(2)-completo	L-completo
+	C=L-completo	L-completo
∪,∩,−,×	PSPACE-completo	PSPACE-completo
∪,∩,×	PSPACE-completo	ΠP2-completo
∪,×	ΠP2-completo	ΠP2-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

• Predefinição:Citation

• Predefinição:Citation

Ligações externas

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