Exemple démontrant la puissance de circuits non déterministes

Un circuit booléen non déterministe possède, en plus des entrées ordinaires , un ensemble d'entrées "non déterministes" . Un circuit non déterministe accepte l'entrée s'il existe tel que la sortie du circuit sur . Analogue à (la classe de langues décidables par des circuits de taille polynomiale), peut être définie comme la classe de langues décidables par des circuits non déterministes de taille polynomiale. Il est largement admis que les circuits non déterministes sont plus puissants que les circuits déterministes, en particuliery = ( y 1 , … , y m ) C x y 1 ( x , y ) P / p o l y N P / p o l y N P ⊂ P / p o l $x = (x_1,\dots,x_n)$$y=(y_1,\dots,y_m)$$C$$x$$y$$1$$(x,y)$$P/poly$$NP/poly$$NP \subset P/poly$ impliquent que la hiérarchie polynomiale s'effondre.

Existe-t-il un exemple explicite (et inconditionnel) dans la littérature montrant que les circuits non déterministes sont plus puissants que les circuits déterministes?

En particulier, connaissez-vous une famille de fonctions calculable par des circuits non déterministes de taille , mais non calculable par des circuits déterministes de taille ?$\{f_n\}_{n > 0}$$cn$$(c+\epsilon)n$

Si ce problème n'a pas progressé, j'ai une réponse.

-

J'ai également pris en compte ce problème depuis mon article COCOON'15 (avant votre question).

Maintenant, j'ai une stratégie de preuve, et elle donne immédiatement le théorème suivant: Il y a une fonction booléenne telle que la complexité non déterministe du circuit U 2 de f est au plus 2 n + o ( n ) et le circuit déterministe U 2 la complexité de f est 3 n - o ( n ) .$f$$U_2$$f$$2n + o(n)$$U_2$$f$$3n - o(n)$

Je m'excuse de ne pas avoir rédigé le document. Le croquis de preuve ci-dessous pourrait suffire à expliquer ma stratégie de preuve. Mon objectif est de rédiger l'article avec plus de résultats d'ici la date limite STACS (1er octobre).

[Croquis de preuve]

Soit .$f = \lor_{i=0}^{\sqrt{n}-1}{Parity_{\sqrt{n}}(x_{\sqrt{n} \cdot i + 1}, \ldots, x_{\sqrt{n} \cdot i + \sqrt{n}}})$

La preuve déterministe de la borne inférieure est basée sur une méthode d'élimination de porte standard avec une petite modification.

La preuve de borne supérieure non déterministe est une construction d'un tel circuit non déterministe.

1. Construire un circuit informatique . (Le nombre de portes esto(n).)$Parity_{\sqrt{n}}$$o(n)$
2. Construire un circuit en sélectionnant entrées de façon non déterministe. (Le nombre de portes est de2n+o(n).)$\sqrt{n}$$2n + o(n)$
3. Combinez les deux circuits.