Um circuito booleano não determinístico possui, além das entradas ordinárias , um conjunto de entradas "não determinísticas" . Um circuito não determinístico aceita a entrada se existir modo que a saída do circuito esteja ligada . Análoga a (a classe de linguagens decidíveis por circuitos polinomiais de tamanho), pode ser definida como a classe de linguagens decidível por circuitos não determinísticos de tamanho polinomial. Acredita-se amplamente que os circuitos não determinísticos são mais poderosos que os circuitos determinísticos, em particulary = ( y 1 , … , y m ) implica que a hierarquia polinomial entra em colapso.
Existe um exemplo explícito (e incondicional) na literatura mostrando que os circuitos não determinísticos são mais poderosos que os circuitos determinísticos?
Em particular, você conhece uma família de funções computável por circuitos não determinísticos de tamanho , mas não computável por circuitos determinísticos de tamanho ?
fonte
Respostas:
Se este problema não tiver progresso, eu tenho uma resposta.
-
Eu também considerei esse problema desde meu artigo sobre o COCOON'15 (antes da sua pergunta).
Agora, eu tenho uma estratégia de prova, e ela imediatamente fornece o seguinte teorema: Existe uma função booleana tal que a complexidade não determinística de -circuito de seja no máximo e a complexidade determinística de -circuito de é .U 2 f 2 n + o ( n ) U 2 f 3 n - o ( n )f U2 f 2n+o(n) U2 f 3n−o(n)
Peço desculpas por não ter escrito o jornal. O esboço de prova abaixo pode ser suficiente para explicar minha estratégia de prova. Pretendo escrever o artigo com mais resultados dentro do prazo do STACS (1º de outubro).
[Esboço de prova]
Seja .f=∨n√−1i=0Parityn√(xn√⋅i+1,…,xn√⋅i+n√)
A prova determinística do limite inferior é baseada em um método padrão de eliminação de gate com uma pequena modificação.
A prova do limite superior não determinístico é uma construção desse circuito não determinístico.
fonte