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 , quase todas as funções booleanas com complexidade de fórmula no máximo têm complexidade de circuito pelo menos .
A prova consiste em derivar um limite inferior em , o número de funções booleanas em entradas calculadas por fórmulas de tamanho . Ao comparar com o número de circuitos de tamanho , que é no máximo , pode-se perceber que, para grandes , , 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 com entradas não determinísticas não é muito maior que o número de circuitos determinísticos de tamanho (para não muito grande, digamos ) Portanto, acho que o seguinte corolário é válido:
Corolário: Para cada constante , quase todas as funções booleanas com complexidade de fórmula no máximo têm complexidade de circuito não determinística pelo menos (para circuitos não determinísticos com 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 ) ).
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.
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.)
fonte