# 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$^1$-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 coNEXP | Π$^P$$_2$-completo |
| ∪,+,× | NEXPTIME-difícil, em coNEXP | Π$^P$$_2$-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$$_2$-completo |
| ∪,+ | Π$^P$$_2$-completo | Π$^P$$_2$-completo |
| ∩,+ | coC$_=$L(2)-completo | L-completo |
| + | C$_=$L-completo | L-completo |
| ∪,∩,−,× | PSPACE-completo | PSPACE-completo |
| ∪,∩,× | PSPACE-completo | Π$^P$$_2$-completo |
| ∪,× | Π$^P$$_2$-completo | Π$^P$$_2$-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 |