Przykład demonstrujący moc obwodów niedeterministycznych

Niedeterministyczny obwód boolowski ma, oprócz zwykłych danych wejściowych , zbiór danych „niedeterministycznych” . Niedeterministyczny obwód przyjmuje wejście jeśli istnieje takie, że wyjście obwodu włączone . Analogicznie do $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 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 , ale nie obliczalną przez deterministyczne obwody o wielkości ? $\{f_n\}_{n > 0}$ $cn$ $(c+\epsilon)n$

cc.complexity-theory circuit-complexity nondeterminism

— Gustav Nordh
źródło

Nie sądzę, że taka rodzina jest znana. Oto najnowszy artykuł badający obwody niedeterministyczne: arxiv.org/abs/1504.06731 Pamiętam, że przed opublikowaniem artykułu Hiroki zadał podobne pytanie tutaj

— Alexander S. Kulikov

Dzięki. Zakładam, że pytanie, do którego się odwołujesz, brzmi: cstheory.stackexchange.com/q/25736, który jest powiązany, ale pyta o dolne granice złożoności obwodu niedeterministycznego.

— Gustav Nordh

Jedną ważną właściwością obwodów niedeterministycznych jest to, że zawsze można je przekształcić w równoważne obwody głębokości-2 poprzez dodanie większej liczby niedeterministycznych danych wejściowych, stosując te same pomysły, co w przypadku redukcji z CircuitSAT do SAT. W szczególności oznacza to, że niedeterministyczne obwody o głębokości 2 mogą obliczać parzystość n bitów o wielkości wielomianowej, podczas gdy deterministyczne obwody o głębokości 2 obliczającej parzystość muszą mieć rozmiar 2 ^ n-1.

— Lub Meir

Słuszna uwaga! Zwłaszcza w odniesieniu do wyżej wspomnianego wyniku Hiroki'ego, że niedeterministyczna złożoność obwodu parzystości wynosi 3 (n-1), co jest równe deterministycznej złożoności obwodu parzystości.

— Gustav Nordh

Przypadek wzorów DeMorgan jest podobny do wymienionych powyżej obwodów o głębokości 2. Niedeterministyczne formuły DeMorgan mogą obliczyć parzystość n bitów w rozmiarze liniowym, wykorzystując podobne idee jak obwody głębokości-2, podczas gdy deterministyczne formuły DeMorgan potrzebują kwadratowej wielkości według twierdzenia Chrapczenki.

— Hiroki Morizumi,

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ść obwodu wynosi co najwyżej a deterministyczny obwód złożoność wynosi . $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.

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

— Hiroki Morizumi
źródło

Coś jest nie tak z granicami. Złożoność niedeterministyczna nie może być większa niż złożoność deterministyczna.

— Emil Jeřábek wspiera Monikę

Dziękuję za odpowiedź, dokładnie tego, czego szukałem!

— Gustav Nordh,