Przykład demonstrujący moc obwodów niedeterministycznych

Niedeterministyczny obwód boolowski ma, oprócz zwykłych danych wejściowych , zbiór danych „niedeterministycznych” y = ( y 1 , … , y m ) . Niedeterministyczny obwód C przyjmuje wejście x, jeśli istnieje y takie, że wyjście obwodu 1 jest włączone ( x , y ) . Analogicznie do P / p o l $x = (x_1,\dots,x_n)$$y=(y_1,\dots,y_m)$$C$$x$$y$$1$$(x,y)$$P/poly$(klasa języków rozstrzygalnych za pomocą wielomianowych obwodów wielkości), można zdefiniować jako klasę języków rozstrzygalnych za pomocą niedeterministycznych obwodów wielkości wielomianowej. Uważa się, że układy nie deterministyczne są silniejsze niż obwody deterministycznych, zwłaszcza N P ⊂ P / P O L Y oznacza, że wielomian hierarchia zwija.$NP/poly$$NP \subset P/poly$

Czy w literaturze istnieje wyraźny (i bezwarunkowy) przykład pokazujący, że obwody niedeterministyczne są silniejsze niż obwody deterministyczne?

W szczególności, czy znasz rodzinę funkcji obliczalną przez niedeterministyczne obwody o wielkości c n , ale nie obliczalną przez deterministyczne obwody o wielkości ( c + ϵ ) n ?$\{f_n\}_{n > 0}$$cn$$(c+\epsilon)n$

Jeśli ten problem nie ma postępu, mam odpowiedź.

-

Rozważyłem również ten problem od czasu mojej pracy COCOON'15 (przed twoim pytaniem).

Teraz mam strategię dowodową i od razu daje następujące twierdzenie: Istnieje funkcja boolowska taka że niedeterministyczna złożoność U 2 obwodu f wynosi co najwyżej 2 n + o ( n ), a deterministyczny obwód U 2 złożoność f wynosi 3 n - o ( n ) .$f$$U_2$$f$$2n + o(n)$$U_2$$f$$3n - o(n)$

Przepraszam, że nie napisałem pracy. Poniższy szkic dowodu może wystarczyć do wyjaśnienia mojej strategii dowodu. Zamierzam napisać artykuł z większą liczbą wyników do terminu STACS (1 października).

[Szkic próbny]

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

Deterministyczny dowód dolnej granicy oparty jest na standardowej metodzie eliminacji bramki z niewielką modyfikacją.

Niedeterministyczny dowód górnej granicy jest konstrukcją takiego niedeterministycznego obwodu.

1. Zbuduj obwód obliczeniowy . (Liczba bramek too(n).)$Parity_{\sqrt{n}}$$o(n)$
2. $\sqrt{n}$$2n + o(n)$
3. Połącz dwa obwody.