Przykład demonstrujący moc obwodów niedeterministycznych

17

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 yx=(x1,,xn)y=(y1,,ym)Cxy1(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/polyNPP/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 ?{fn}n>0cn(c+ϵ)n

Gustav Nordh
źródło
4
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
2
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
3
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
1
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
1
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,

Odpowiedzi:

4

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 ) .fU2f2n+o(n)U2f3no(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=i=0n1Parityn(xni+1,,xni+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).)Parityno(n)
  2. n2n+o(n)
  3. 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,