Complexidade de circuitos

No ramo da Ciência da computação teórica, complexidade de circuitos é um ramo da Teoria da complexidade computacional onde Função booleanas são classificadas de acordo com o tamanho ou o grau dos Circuitos booleanos que as computam. Ele trata da complexidade de um circuito Booleano. Uma noção é a complexidade do circuito de uma linguagem recursiva que é decidida por uma família de circuitos $C_{1},C_{2},\ldots$ (veja mais a seguir).

Um circuito booleano com $n$ bits de entrada é um grafo acíclico dirigido onde cada nó (normalmente chamados de porta neste contexto) é um desses quatro elementos: um nó de entrada cujo grau de entrada é 0 representado por um dos $n$ bits de entrada, uma porta AND, uma porta OR ou uma porta NOT. Uma dessas portas é designada porta de saída. Tal circuito naturalmente computa uma função a partir de suas $n$ entradas. O tamanho de um circuito é o numero de portas que ele contém seu grau é definido pelo comprimento do maior caminho de uma porta de entrada até uma porta de saída.

Existem dois conceitos principais da complexidade de circuitos (esses dois conceitos são definidos no Sipser (1997)). A complexidade do tamanho do circuito de uma função Booleana $f$ é o tamanho mínimo de qualquer circuito que compute $f$. A complexidade do grau do circuito de uma função Booleana $f$ é o grau mínimo de qualquer circuito que compute $f$.

Essas noções também se aplicam quando se considera a complexidade do circuito de uma linguagem recursiva: Uma linguagem formal pode conter muitas palavras com uma quantidade diversa de bits por palavra. Circuitos booleanos, no entanto, só permitem um número fixo de bits por entrada. Logo, nenhum circuito booleano é capaz de decidir sozinho uma linguagem recursiva. Para permitir que isso seja feito, deve-se considerar famílias de circuitos $C_{1},C_{2},\ldots$ onde cada $C_{n}$ aceita entradas de tamanho $n$. Cada família de circuito vai naturalmente gerar uma linguagem recursiva ao dar como saída $1$ quando uma palavra for membro da família, e $0$ caso contrário. Dizemos que uma família de circuitos tem tamanho mínimo se não existe outra família que decida com um circuito menor do que o tamanho de $C_{n}$, para entradas de tamanho $n$. O mesmo se aplica para famílias de grau mínimo.

Sendo assim, a complexidade do tamanho do circuito de uma linguagem recursiva $A$ é definia como a função $t:\mathbb {N} \to \mathbb {N}$, que relaciona o tamanho dos bits de uma entrada, $n$, com a complexidade do tamanho de um circuito mínimo $C_{n}$ que decide se entradas desse tamanho estão em $A$. A complexidade do grau do circuito é definida similarmente.

Classe de complexidades definida em termos de circuitos booleanos incluem AC⁰, AC, TC⁰ e NC.

Uniformidade

Circuitos booleanos são os principais exemplos dos chamados modelos de computação não-uniformes, no sentindo de que entradas de diferentes tamanhos são processadas por circuitos diferentes, em contraste com modelos uniformes como as Máquinas de Turing, onde o mesmo dispositivo computacional é usado para todos os possíveis tamanhos de entrada. Dessa forma, um problema computacional particular é associado a uma família específica de circuitos Booleanos $C_{1},C_{2},\dots$ onde cada $C_{n}$ é o circuito que trata as entradas de n bits. Uma condição de uniformidade é usualmente imposta nessas famílias, sendo necessária a existência de algum Autômato linearmente limitado que dada uma entrada n produza uma descrição do circuito $C_{n}$. Quando este Autômato roda em um tempo de execução polinomial n, a família do circuito é ditar ser P-uniforme. A exigência mais rigorosa da uniformidade DLOGTIME é de particular interesse no estudo da profundidade de classes de circuito como AC⁰ ou TC⁰.

Uniformidade de tempo Polinomial

Uma família de circuitos booleanos $\{C_{n}:n\in \mathbb {N} \}$ é uniforme em tempo polinomial se existe uma Máquina de Turing determinística M, tal que

• M roda em tempo polinomial
• Para todo $n\in \mathbb {N}$, M dá como saída a descrição de $C_{n}$ dada a entrada $1^{n}$ .

Uniformidade LSPACE

Uma família de circuitos booleanos $\{C_{n}:n\in \mathbb {N} \}$ é logspace uniforme se existe uma Máquina de Turing determinística M, tal que

• M roda em um espaço logarítmico
• Para todo $n\in \mathbb {N}$, M dá como saída a descrição de $C_{n}$ dada a entrada $1^{n}$.

História

A Complexidade de circuitos teve início com Shannon (1949), provando na ocasião que quase todas as funções booleanas sobre n variáveis exigem circuitos de tamanho Θ (2 ⁿ/n). Apesar deste fato, os teóricos da complexidade não foram capaz de provar limites inferiores de circuitos superpolinomiais para funções Booleanas específicas.

Por outro lado, os limites inferiores superpolinomiais foram provados sobre determinadas restrições na família dos circuitos utilizados. A primeira função para a qual os limites inferiores de circuito superpolinomial foram mostradas foi a função paridade, que calcula a soma dos seus bits de entrada módulo 2. O fato de que a paridade não está contida em AC⁰ foi primeiramente estabelecida de forma independente por Ajtai (1983) e por Furst, Saxe and Sipser (1984). Melhoramentos posteriores feitos por Håstad (1987) estabeleceram de fato que qualquer família de circuitos de grau constante que computam a função de paridade requerem tamanho exponencial. Smolensky (1987) provou que isto é verdade mesmo se o circuito for incrementado com mais portas para computar a soma dos bits de entrada módulo algum número primo p.

O k-clique é o problema de decidir se um determinado grafo de n vértices tem um clique de tamanho k. Para qualquer escolha particular das constantes n e k, o grafo pode ser codificado em binário utilizando ${n \choose 2}$ bits que indicam para cada aresta se ela está presente ou não. O problema k-clique pode ser formalizado como a função $f_{k}:\{0,1\}^{n \choose 2}\to \{0,1\}$ tal que $f_{k}$ produz como saída 1 se e somente se o grafo for codificado por uma string que contém um clique de tamanho k. Esta família de funções é monótona e pode ser computada por uma família de circuitos, mas já foi mostrado que ela não pode ser computada por uma família de tamanho polinomial de circuitos monótonos (ou seja, circuitos com portas AND e OR mas sem a porta NOT). O resultado original de Razborov (1985) foi posteriormente melhorado para um limite inferior de tamanho exponencial por Alon and Boppana (1987). Rossman (2008) mostrou que circuitos de grau contante com portas AND, OR, e NOT requerem tamanho $\Omega (n^{k/4})$ para resolver o problema k-clique mesmo na complexidade de caso médio. Além disso, existe um circuito de tamanho $n^{k/4+O(1)}$ que computa $f_{k}$.

Raz e McKenzie posteriormente mostraram que a hierarquia monótona NC é infinita (1999).

O Problema da Divisão Inteira permanece uniforme TC⁰ (Hesse 2001).

Limites Inferiores de Circuitos

Limites inferiores de circuitos são normalmente difíceis de se provar. Resultados conhecidos incluem

• Paridade não é não-uniforme AC⁰, provado por Ajtai (1983) e por Furst, Saxe e Sipser.
• Uniforrmidade TC⁰ não percence a PP, provado por Allender.
• As classes SP
  2, PP and MA/1 (MA com um bit de recomendação) não estão em SIZE(n^k) para uma constante k.
• Enquanto se suspeita que clases não-uniformes ACC⁰ não contenham a maioria das funções, foi só em 2010 Williams provou que ${\mathsf {NEXP}}\not \subseteq {\mathsf {ACC}}^{0}$.

Está em aberto o problema de dizer se NEXPTIME possui não-uniformidade de circuito TC⁰.

Provas de limites inferiores de circuitos estão fortemente conectadas a desrandomização. Uma prova de que P = BPP implicaria que ou ${\mathsf {NEXP}}\not \subseteq {\mathsf {P/poly}}$ ou que permanentemente não pode ser computada por um circuito aritmético não-uniforme (polinomial) de tamanho polinomial e grau polinomial.

Classes de Complexidade

Muitas classes de complexidade de circuito são definidas em termos de hierarquia de classes. Para cada inteiro não-negativo i, existe uma classe NCⁱ, que consiste dos circuitos de tamanho polinomial de grau $O(\log ^{i}(n))$, usando portas AND, OR, e NOT limitadas. Podemos falar da união NC de todas essas classes. Considerando portas não limitadas, construímos as classes ACⁱ e AC. Podemos construir muitos outras classes de complexidade com as mesmas restrições de tamanho e grau através da permissão de tamanhos diferentes de conjuntos de portas.

Relação com a complexidade de tempo

Digamos que uma certa linguagem, $A$, pertence a Classe de complexidade de tempo ${\text{TIME}}(t(n))$ para uma função $t:\mathbb {N} \to \mathbb {N}$. Então $A$ é de complexidade de tempo ${\mathcal {O}}(t^{2}(n))$

Bibliografia

• Ajtai, Miklós (1983). «$\Sigma _{1}^{1}$-formulae on finite structures». Annals of Pure and Applied Logic. 24: 1–24. doi:10.1016/0168-0072(83)90038-6 
• Alon, Noga; Boppana, Ravi B. (1987). «The monotone circuit complexity of Boolean functions». Combinatorica. 7 (1): 1–22. doi:10.1007/bf02579196 
• Furst, Merrick L.; Saxe, James B.; Sipser, Michael (1984). «Parity, circuits, and the polynomial-time hierarchy». Mathematical Systems Theory. 17 (1): 13–27. doi:10.1007/bf01744431 
• Håstad, Johan (1987), Computational limitations of small depth circuits (PDF), Ph.D. thesis, Massachusetts Institute of Technology. 
• Hesse, William (2001). «Division is in uniform TC⁰». Proc. 28th International Colloquium on Automata, Languages and Programming. Springer. pp. 104–114 
• Raz, Ran; McKenzie, Pierre (1999). «Separation of the monotone NC hierarchy». Combinatorica. 19 (3): 403–435. doi:10.1007/s004930050062 
• Razborov, Alexander A. (1985). «Lower bounds on the monotone complexity of some Boolean functions». Mathematics of the USSR, Doklady. 31: 354–357 
• Rossman, Benjamin (2008). «On the constant-depth complexity of k-clique». STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing. ACM. pp. 721–730. doi:10.1145/1374376.1374480 
• Shannon, Claude E. (1949). «The synthesis of two-terminal switching circuits». Bell System Technical Journal. 28 (1): 59–98. doi:10.1002/j.1538-7305.1949.tb03624.x 
• Smolensky, Roman (1987). «Algebraic methods in the theory of lower bounds for Boolean circuit complexity». Proc. 19th Annual ACM Symposium on Theory of Computing. ACM. pp. 77–82. doi:10.1145/28395.28404 
• Vollmer, Heribert (1999). Introduction to Circuit Complexity: a Uniform Approach. [S.l.]: Springer Verlag. ISBN 3-540-64310-9 
• Wegener, Ingo (1987). The Complexity of Boolean Functions. [S.l.]: John Wiley and Sons Ltd, and B. G. Teubner, Stuttgart. ISBN 3-519-02107-2  At the time an influential textbook on the subject, commonly known as the "Blue Book". Also available for download (PDF) at the Electronic Colloquium on Computational Complexity.
• Lecture notes for a course of Uri Zwick on circuit complexity
• Circuit Complexity before the Dawn of the New Millennium, a 1997 survey of the field by Eric Allender slides.