O não determinismo é, em média, inútil para circuitos?

8

Savický e Woods (o número de funções booleanas calculadas por fórmulas de um determinado tamanho) provam o seguinte resultado.

Teorema [SW98]: Para cada constante k>1 , quase todas as funções booleanas com complexidade de fórmula no máximo nk têm complexidade de circuito pelo menos nk/k .

A prova consiste em derivar um limite inferior em B(n,nk) , o número de funções booleanas em n entradas calculadas por fórmulas de tamanho nk . Ao comparar B(n,nk) com o número de circuitos de tamanho C=nk/k , que é no máximo CCeC+4n , pode-se perceber que, para grandes n , CCeC+4n<<B(n,nk), e o resultado segue.

Parece-me que o resultado poderia ser fortalecido observando que o número de circuitos não determinísticos de tamanho nk com m entradas não determinísticas não é muito maior que o número de circuitos determinísticos de tamanho nk (para m não muito grande, digamos m=n ) Portanto, acho que o seguinte corolário é válido:

Corolário: Para cada constante k>1 , quase todas as funções booleanas com complexidade de fórmula no máximo nk têm complexidade de circuito não determinística pelo menos nk/k (para circuitos não determinísticos com n entradas não determinísticas).

(Lembre-se de que um circuito não determinístico possui, além das entradas comuns , um conjunto de entradas "não determinísticas" y = ( y 1 , , y m ) . Um circuito não determinístico C aceita entrada x se existir y, de modo que o circuito emita 1 em ( x , y ) ).x=(x1,,xn)y=(y1,,ym)Cxy1(x,y)

Obviamente, o limite inferior em também é um limite inferior no número de funções booleanas em n entradas calculadas por circuitos de tamanho n k , portanto, "complexidade da fórmula no máximo n k " pode ser substituída por "circuito complexidade no máximo n k "no corolário. O corolário também pode ser declarado como: para funções com complexidade de circuitos polinomiais, a mudança para circuitos não determinísticos não pode, em média, diminuir a complexidade em mais do que um fator constante.B(n,nk)nnknknk

Questões:

(1) Existem implicações / consequências interessantes do corolário acima?

(2) Existem outros resultados na mesma direção? Por exemplo, o que se sabe sobre a seguinte proposição? Para problemas em P, a mudança de TMs para NTMs não pode, em média, diminuir a complexidade em mais do que um fator constante.

(Gil Kalai também tem uma pergunta um pouco relacionada a essa.)

Gustav Nordh
fonte

Respostas:

8

1) Perceba que o não determinismo é um arenque vermelho aqui. Você poderia ter usado alternância ou circuitos com portas que resolvem o problema da parada. Tudo se resume a um argumento de contagem simples: depois de corrigir o modelo, você só pode calcular funções que têm uma descrição de k bits.2kk

2) Para classes uniformes como P, isso é mais desafiador, pois não há uma definição clara de "função média em P" e os argumentos de contagem não funcionam mais de maneira tão limpa. É consistente com o conhecimento atual que tudo em P pode ser resolvido em tempo linear não determinístico.

Lance Fortnow
fonte
Você tem algum ponteiro para esta última afirmação sobre P e NTIME (n)?
CP
2
Eu quis dizer que é um problema em aberto se P está contido em NTIME (n). O problema é discutido em um artigo de Ravi Kannan ( doi.org/10.1145/800061.808764 ).
Lance Fortnow
2
α ( 0 , 1 ) αPNTIME(nα)α(0,1)α
2
Eu acredito que a função de paridade não pode ser calculada no tempo NTIME ( ) para qualquer . Caso contrário, você teria tamanho de profundidade-2 circuitos para paridade, o que não pode acontecer. α < 1 2 o ( n )nαα<12o(n)
Lance Fortnow
@LanceFortnow Parece que ? P(logn)TIME[polylog(n)]
T ....