Beispiel zur Demonstration der Leistung nicht deterministischer Schaltkreise

Eine nicht deterministische Boolesche Schaltung hat zusätzlich zu den gewöhnlichen Eingängen eine Menge von "nicht deterministischen" Eingängen y = ( y 1 , ... , y m ) . Eine nicht deterministische Schaltung C akzeptiert den Eingang x, wenn es y gibt, so dass die Schaltung 1 an ( x , y ) ausgibt . Analog zu P / p o l $x = (x_1,\dots,x_n)$$y=(y_1,\dots,y_m)$$C$$x$$y$$1$$(x,y)$$P/poly$(die Klasse der Sprachen entscheidbar durch polynomiale Größe Schaltungen), kann als die Klasse von Sprachen definiert sein entscheidbar durch polynomiale Größe nicht-determinis Schaltungen. Es wird allgemein angenommen , dass nicht-deterministische Schaltungen leistungsstärker als deterministische Schaltungen sind insbesondere N P ⊂ P / p o l y impliziert , dass das Polynom Hierarchie zusammenbricht.$NP/poly$$NP \subset P/poly$

Gibt es ein explizites (und unbedingtes) Beispiel in der Literatur, das zeigt, dass nicht deterministische Schaltkreise leistungsfähiger sind als deterministische Schaltkreise?

Insbesondere sind Sie eine Funktion Familie kennen berechenbare von nicht-deterministisch Schaltungen der Größe c n , aber nicht berechenbar durch deterministische Schaltungen der Größe ( c + ε ) n ?$\{f_n\}_{n > 0}$$cn$$(c+\epsilon)n$

Wenn dieses Problem keinen Fortschritt hat, habe ich eine Antwort.

-

Ich habe dieses Problem seit meinem COCOON'15-Artikel (vor Ihrer Frage) ebenfalls berücksichtigt.

$f$$U_2$$f$$2n + o(n)$$U_2$$f$$3n - o(n)$

Ich entschuldige mich, dass ich das Papier nicht geschrieben habe. Die nachstehende Proofskizze könnte ausreichen, um meine Proofstrategie zu erläutern. Ich beabsichtige, die Arbeit mit mehr Ergebnissen bis zum STACS-Stichtag (1. Oktober) zu schreiben.

[Proof-Skizze]

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

Der deterministische Nachweis der unteren Schranke basiert auf einer Standard-Gate-Eliminierungsmethode mit geringfügigen Änderungen.

Der nicht deterministische Beweis der oberen Schranke ist eine Konstruktion einer solchen nicht deterministischen Schaltung.

1. Konstruieren Sie eine Schaltung, die berechnet$Parity_{\sqrt{n}}$$o(n)$
2. $\sqrt{n}$$2n + o(n)$
3. Kombinieren Sie die beiden Kreisläufe.