Mostrar código-fonte de Circuitos e conjuntos de números naturais

'''Circuitos sobre [[Número natural|números naturais]]''' são um modelo matemático utilizado no estudo da [[Complexidade computacional|teoria da complexidade computacional]]. Eles são um caso especial de circuitos. O objeto é classificado como [[Grafos acíclicos dirigidos|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 [[Algoritmo|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 [[Complexidade de circuitos|circuito]], isto é, um g[[Grafos acíclicos dirigidos|rafos 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&#x20;&#x2212;, onde <math /> e as classificações dos nós de grau 2 são de +, ×, ∪ e ∩, onde <math />, <math /> 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 <math />?
* 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 <math />.

=== Restrições ===
Deixe O ser um subconjunto de {∪,∩,&#x2212;,+,×}, 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 (grafo)|á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 <math />e , em seguida, pode-se facilmente provar por indução em <math /> que <math /> , de fato, <math /> e por indução <math />.

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

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.
{| class="wikitable" style="text-align: center; width: 80%; margin-bottom: 10px;"
|+ Complexidade
! scope="col" | O
! scope="col" | MC(O) 
! scope="col" | MF(O)
|-
! scope="row" | ∪,∩,&#x2212;,+,×
| [[NEXPTIME]]-difícil
Decidíveis com uma [[máquina oráculo]] para o [[problema da parada]]
| [[PSPACE]]-difícil
|-
! scope="row" | ∪,∩,+,×
| [[NEXPTIME]]-completo
| [[NP-completo]]
|-
! scope="row" | ∪,+,×
| [[PSPACE]]-completo
| [[NP-completo]]
|-
! scope="row" | ∩,+,×
| [[P (complexidade)|P]]-difícil, em co-R
| LOGCFL
|-
! scope="row" | +,×
| [[P (complexidade)|P]]-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∪,∩,&#x2212;,+
| [[PSPACE]]-completo
| [[PSPACE]]-completo
|-
! scope="row" | ∪,∩,+
| [[PSPACE]]-completo
| [[NP-completo]]
|-
! scope="row" | ∪,+
| [[NP-completo]]
| [[NP-completo]]
|-
! scope="row" | ∩,+
| C<sub>=</sub>L-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | +
| C<sub>=</sub>L-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∪,∩,&#x2212;,×
| [[PSPACE]]-completo
| [[PSPACE]]-completo
|-
! scope="row" | ∪,∩,×
| [[PSPACE]]-completo
| [[NP-completo]]
|-
! scope="row" | ∪,×
| [[NP-completo]]
| [[NP-completo]]
|-
! scope="row" | ∩,×
| C<sub>=</sub>L-difícil, em [[P (complexidade)|P]]
| [[LSPACE|L]]-completo
|-
! scope="row" | ×
| [[Complexidade NL|NL]]-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∪,∩,&#x2212;
| [[P (complexidade)|P]]-completo
| [[NC (complexidade)|NC<sup>1</sup>]]-completo
|-
! scope="row" | ∪,∩
| [[P (complexidade)|P]]-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∪
| [[Complexidade NL|NL]]-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∩
| [[Complexidade NL|NL]]-completo
| [[LSPACE|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 .<ref>{{Citation|author1=Christian Glaßer|author2=Katrin Herr|author3=Christian Reitwießner|author4=Stephen Travers|author5=Matthias Waldherr|title=Equivalence Problems for Circuits over Sets of Natural Numbers|journal=Lecture Notes in Computer Science|volume=Volume 4649/2007|edition=(what is called "number" in bibtex)|year=2007|isbn=978-3-540-74509-9|pages=127–138|doi=10.1007/978-3-540-74510-5|publisher=Springer|place=Berlin / Heidelberg|url=http://www.springerlink.com/content/c007kk787054v746/}}</ref> 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.
{| class="wikitable" style="text-align: center; width: 80%; margin-bottom: 10px;"
|+ Complexidade
! scope="col" | O
! scope="col" | EC(O) 
! scope="col" | EF(O)
|-
! scope="row" | ∪,∩,&#x2212;,+,×
| [[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]]
|-
! scope="row" | ∪,∩,+,×
| [[NEXPTIME]]-difícil, em co[[NEXPTIME|NEXP]]<sup>[[NP (complexidade)|NP]]</sup>
| [[Hierarquia polinomial|Π<sup>P</sup><sub>2</sub>]]-completo
|-
! scope="row" | ∪,+,×
| [[NEXPTIME]]-difícil, em co[[NEXPTIME|NEXP]]<sup>[[NP (complexidade)|NP]]</sup>
| [[Hierarquia polinomial|Π<sup>P</sup><sub>2</sub>]]-completo
|-
! scope="row" | ∩,+,×
| [[P (complexidade)|P]]-difícil, em [[BPP]]
| [[LSPACE|L]]-difícil, em LOGCFL
|-
! scope="row" | +,×
| [[LSPACE|L]]-difícil, em LOGCFL
| [[P (complexidade)|P]]-difícil, em co[[RP (complexidade computacional)|RP]]
|-
! scope="row" | ∪,∩,&#x2212;,+
| [[PSPACE]]-completo
| [[PSPACE]]-completo
|-
! scope="row" | ∪,∩,+
| [[PSPACE]]-completo
| [[Hierarquia polinomial|Π<sup>P</sup><sub>2</sub>]]-completo
|-
! scope="row" | ∪,+
| [[Hierarquia polinomial|Π<sup>P</sup><sub>2</sub>]]-completo
| [[Hierarquia polinomial|Π<sup>P</sup><sub>2</sub>]]-completo
|-
! scope="row" | ∩,+
| coC<sub>=</sub>L(2)-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | +
| C<sub>=</sub>L-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∪,∩,&#x2212;,×
| [[PSPACE]]-completo
| [[PSPACE]]-completo
|-
! scope="row" | ∪,∩,×
| [[PSPACE]]-completo
| [[Hierarquia polinomial|Π<sup>P</sup><sub>2</sub>]]-completo
|-
! scope="row" | ∪,×
| [[Hierarquia polinomial|Π<sup>P</sup><sub>2</sub>]]-completo
| [[Hierarquia polinomial|Π<sup>P</sup><sub>2</sub>]]-completo
|-
! scope="row" | ∩,×
| coC<sub>=</sub>L(2)-difícil, em [[P (complexidade)|P]]
| [[LSPACE|L]]-completo
|-
! scope="row" | ×
| C<sub>=</sub>L-difícil, em [[P (complexidade)|P]]
| [[LSPACE|L]]-completo
|-
! scope="row" | ∪,∩,&#x2212;
| [[P (complexidade)|P]]-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∪,∩
| [[P (complexidade)|P]]-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∪
| [[Complexidade NL|NL]]-completo
| [[LSPACE|L]]-completo
|-
! scope="row" | ∩
| [[Complexidade NL|NL]]-completo
| [[LSPACE|L]]-completo
|}

== Referências ==
{{Reflist}}
* {{Citation|last=Travers|first=Stephen|year=2006|title=The Complexity of Membership Problems for  Circuits over Sets of Natural Numbers|publisher=Theoretical Computer Science|volume=389|issue=1|pages=211–229|url=http://portal.acm.org/citation.cfm?id=1238761|issn=0304-3975|ref=travers}}

* {{Citation|author1=Pierre McKenzie|author2=Klaus W. Wagner|title=The Complexity of Membership Problems for Circuits over Sets of Natural Numbers|journal=Lecture Notes In Computer Science|volume=2607|year=2003|isbn=3-540-00623-0|pages=571–582|publisher=Springer-Verlag|url=http://portal.acm.org/citation.cfm?id=646517.696311}}

== Ligações externas ==
* Pierre McKenzie, [http://www.iro.umontreal.ca/~mckenzie/Dagstuhl02.pdf A complexidade do circuito de avaliação sobre os números naturais]
[[Categoria:Aritmética]]
[[Categoria:Teoria da complexidade computacional]]