Complexidade do circuito computado de problemas de decisão

9

Alguém já explorou qual é a complexidade do circuito de problemas clássicos de decisão, como Primes ou Isomorfismo de Gráfico, para o tamanho pequeno de entrada ? $N$

Enquanto a maioria das pessoas está interessada em saber como a escala vai como , acho que também seria interessante ver como isso cresce para N. pequeno. Claro, agora sabemos que Primes está em P, mas seria interessante ver como cresce, e talvez até mudanças bruscas na taxa de crescimento do gráfico, à medida que as entradas aumentam o suficiente para que um algoritmo diferente se torne mais eficiente. $N \to \infty$

Existe até a possibilidade (improvável) de que alguém possa extrair de uma sequência de circuitos um algoritmo geral.

Parece que essa abordagem pode responder a perguntas diferentes das geralmente feitas sobre . Com os avanços do conhecimento de algoritmos (solucionadores SAT, etc.) e do poder da super computação, respostas concretas podem ser obtidas para pequeno . $N \to \infty$ $N$

Existem referências ou listas de resultados para pessoas que explicitamente calculam a complexidade do circuito de problemas de decisão para pequeno ? $N$

Se houver pessoas trabalhando nisso, que algoritmos eles usam atualmente para resolver o problema mínimo de circuito (dada uma função booleana e um conjunto de portas, produza um circuito usando o número mínimo de portas necessário)?

cc.complexity-theory reference-request circuit-complexity TigerSpots
fonte

parece quase impossível atacar a partir dessa direção, porque nem mesmo é possível calcular circuitos ideais para problemas muito "pequenos". isso parece ser basicamente o resultado da complexidade de kolmogorov. uma outra direção aparentemente promissora / equivalente, pouco conhecida ou muito estudada, é via complexidade gráfica, que parece permitir o estudo de problemas "menores", mas ainda com grandes implicações, por exemplo, nas separações de classes de complexidade ... também conhecido como "lema da ampliação" etc

vzn

7

Sim, essa é uma ideia natural e as pessoas pensaram nisso. Em suma, o problema é que mesmo os solucionadores de SAT / QBF de ponta permitem encontrar apenas circuitos muito pequenos (com cerca de 10 a 12 portas), sem falar em provar que não há um circuito pequeno. Algumas referências:

Ryan Williams, Aplicando a prática à teoria (2008):

Nosso conhecimento da complexidade do circuito booleano é bastante pobre. <...> Uma boa razão pela qual não sabemos muito sobre a verdadeira potência dos circuitos é que não temos muitos exemplos de circuitos mínimos. Não sabemos, por exemplo, que um circuito ideal para olhares multiplicação de matrizes booleanas como. $3 \times 3$

$3 \times 3$ $10 \times 10$ Parece multiplicação de matrizes booleanas? Eles são regulares na estrutura? É provável que as respostas dêem informações valiosas sobre a complexidade do problema. Os melhores algoritmos que conhecemos reduzem o problema à multiplicação de matrizes em um anel, que é então resolvido por uma construção recursiva altamente regular (como Strassen [Str69]). Mesmo que os circuitos catalogados não sejam realmente mínimos, mas próximos disso, exemplos concretos de pequenas entradas podem ser úteis para os teóricos buscarem inspiração, ou talvez para computadores buscarem padrões através de técnicas de aprendizado de máquina. O poder de pequenos exemplos não pode ser subestimado.

$2 \times 2$ $3 \times 3$ $3 \times 3$

2.5 n \leq C (M O D_{3}) \leq 3 n

$2.5n \le C(MOD_3) \le 3n$

2 n \leq C (A N D, O R, X O R) \leq 2.5 n

$2n \le C(AND,OR,XOR) \le 2.5n$

Os Exercícios 477-481 na Seção 7.2.2.2: Satisfação do Volume 4 da TAOCP por Don Knuth (2015) discutem maneiras de encontrar circuitos ideais com a ajuda dos solucionadores SAT. Da solução para o exercício 481:

$n \le 5$ $n=6$ $a=0$ $n=6$ $a \neq 0$

Alexander S. Kulikov
fonte

5

Em muitos modelos não uniformes - circuitos booleanos, circuitos algébricos, árvores de decisão, programas de ramificação etc. - calcular a complexidade exata parece ser significativamente mais difícil do que calcular a complexidade assintótica. Embora tenha esperança de que sua intuição esteja correta - que entender a complexidade exata de pequenas instâncias possa levar a insights assintóticos - conheço apenas alguns casos em que isso aconteceu:

Algoritmos e limites inferiores para multiplicação matricial de pequenos formatos. Houve bastante trabalho em 2x2 ( Strassen ), 3x3 ( Laderman ) e outros pequenos formatos para multiplicação de matrizes (veja também Johnson-McLoughlin e Hopcroft-Kerr ). Originalmente, eles costumavam ser usados para fornecer melhorias assintóticas, devido à estrutura recursiva da multiplicação da matriz. Eventualmente, Coppersmith-Winograd suplantou tudo isso no reino assintótico.
Os limites inferiores do estilo GCT na multiplicação de pequenas matrizes devido a Bürgisser e Ikenmeyer produziram limites inferiores assintóticos na multiplicação de matrizes. Eu acho que isso é pelo menos parcialmente porque a estrutura teórica da representação sugere naturalmente como transformar um único limite inferior exato em uma família infinita.
(Veja a resposta de Alexander Kulikov para mais algumas)

Além disso, houve uma quantidade pequena, mas não trivial, de trabalho sobre a complexidade exata de vários problemas, mas a maioria dos problemas é mais fácil do que GraphIso ou Primes (exceto o último exemplo da permanente). Embora eu ache este trabalho interessante e mantenho a esperança de que leve a insights teóricos mais amplos, até onde sei, ainda não o fez.

$n$
Também houve algum trabalho em redes exatas de classificação de profundidade mínima ( Bundala e Závodný parecem ser as mais recentes).
$2^k$
$per_3$

Joshua Grochow
fonte

Complexidade do circuito computado de problemas de decisão

Respostas: