Qual é a menor classe de complexidade para a qual um circuito superlinear é conhecido?

25

Desculpas por fazer uma pergunta que certamente deve estar em muitas referências padrão. Estou curioso sobre exatamente a pergunta no título, em particular estou pensando em circuitos booleanos, sem limite de profundidade. Coloquei "menor" entre aspas para permitir a possibilidade de haver várias classes diferentes, não conhecidas por se incluirem, pelas quais um limite superlinear é conhecido.

hastings mate
fonte

Respostas:

25

Acredito que as menores classes conhecidas são (Cai, 2001), (Vinodchandran, 2005) e (Santhanam, 2007). Sabe-se que todos estes não estão em para cada constante .P P ( M A c o M A ) / 1 S I Z E ( n k ) kS2PPP(MAcoMA)/1SIZE(nk)k

Ryan O'Donnell
fonte
1
Obrigado a todos pelas respostas. Estou aceitando o Ryan, pois ele tem a maior variedade de resultados, mas agradeço a Robin e Kaveh pelas explicações detalhadas.
Matt Hastings
20

O resultado mais forte que eu sou em conta é que, para todos os k, existe um problema em S2P que requer circuitos de tamanho Ω(nk) .

é uma classe contida em Z P P N P , que é ela própria dentro de Σ P 2¸ P 2 . (Ozoológico de complexidadetem mais informações sobre essa classe.)S2PZPPNPΣ2PΠ2P

O resultado decorre da versão mais forte do teorema de Karp-Lipton, devido a Cai .

Uma prova rápida de como isso decorre do teorema KL: Primeiro, se SAT requer circuitos de tamanho super-polinomiais, estamos a fazer, uma vez que já exibiu um problema na que precisa de circuitos de tamanho super-polinomiais. Se SAT possui circuitos de tamanho polinomial, então, pela versão mais forte do teorema de Karp-Lipton, o PH entra em colapso para S P 2 . Sabemos que o PH contém problemas como esses (pelo resultado de Kannan), e, portanto, o S P 2 contém esse problema.S2PS2PS2P

Robin Kothari
fonte
3
Uma resposta agradável e superior, como sempre. :)
Kaveh
13

Σ2pΠ2pΩ(nk)PH

NP5n

Veja o livro de Arora e Barak, página 297. Richard J. Lipton publicou em seu blog um post sobre esses resultados, veja também este .

Kaveh
fonte
1

S2Pk1c
O~(nk)
O2PO~(nk2)O(nk(logn)c)

O2PO~(nk2+k)iO~(nmin(k2+k,k3))

Um problema de decisão não computável com circuitos io- é o menor número (consultado usando seus dígitos binários) que não é a tabela verdadeira de um circuito com portas. Se NP estiver em P / poli, o problema terá uma testemunha inconsciente irrefutável, que consiste no seguinte: (1) (2) um circuito que forneceu , mostra que tem um circuito suficientemente pequeno. (3) (usado apenas para o ligado) um verificador que nos permite executar o circuito do oponente por (2) apenas vezes (obtendo 1 bit por corrida )N n k( log n ) c + 1N N < N N ˜ O ( n k 3 ) O ( 1 )O(nk(logn)c)Nnk(logn)c+1
N
N<NN
O~(nk3)O(1)

Em uma nota separada, para cada , existem problemas de decisão em (MA ∩ coMA) / 1 que não possuem circuitos . '/ 1' significa que a máquina recebe um conselho que depende apenas do tamanho da entrada. Além disso, a cadeia de Merlin envia pode ser escolhida a depender apenas do tamanho de entrada (com esta restrição, MA é um subconjunto de ), e o aconselhamento complexidade . A prova (Santhanam 2007) generaliza IP = PSPACE e PSPACE⊂P / poly ⇒ PSPACE = MA usando um certo problema de comportamento completo do PSPACE bem comportado e preenchendo as entradas para obter tamanhos mínimos de circuito que são infinitamente frequentemente entre e , usando conselhos para detectar exemplos suficientes de taisO ( n k ) O 2 P Σ P 2 n k + 1 n k + 2 n nkO(nk)O2PΣ2Pnk+1nk+2n, e para estes , resolvendo o problema acolchoado, fazendo Merlin produzir esse circuito.n

Dmytro Taranovsky
fonte