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, em seguida, isto é  contém primeiros números. Mais uma vez isso pode ser provado por indução sobre ,isso é verdade para  por definição e deixe , dividindo  por  nós vemos que pode ser escrito como  onde , e por indução, e  estão dentro de  , assim certamente .

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

Ligações externas Pierre McKenzie, A complexidade do circuito de avaliação sobre os números naturais Categoria:Aritmética Categoria:Teoria da complexidade computacional