Obwody z wyroczniami a maszyny Turinga z wyroczniami

Mówiąc wprost: jaka jest zgodność między maszynami Turinga z wyroczniami a rodzinami jednorodnych obwodów z wyroczniami? Jak te ostatnie są zdefiniowane w celu uzyskania tego samego modelu obliczeniowego dla danej maszyny Turinga z Oracle?

To może być elementarne pytanie, ale nie jest oczywiste, gdzie szukać, a ja jestem osobą, która lubi upewniać się, że moje fundamenty używają zaprawy dobrej jakości. Jeśli istnieje standardowe odniesienie, proszę o wskazanie mnie. (Na przykład książka Papadimitriou w ogóle nie opisuje obwodów z wyroczniami).

Moja robocza hipoteza jest następująca: rodzina jednorodnych obwodów z dostępem do wyroczni (np. W celu rozwiązania problemu NP-zupełnego) jest zdefiniowana następująco:

Definiuje się nieskończoną rodzina „Oracle bramy” O _n , po jednej dla każdego wymiaru obwodu n, z których każdy obliczania funkcji f _n : {0,1} ^cn → {0,1}, dla pewnej stałej C.
Funkcje f _n obliczone przez bramki wyroczni O _n powinny być „jednolite” w następującym znaczeniu: dla dowolnego n <N i x ∈ {0,1} ⁿ wymagamy f _n ( x ) = f _N (0 ^{c ( N-n)} x ) --- to znaczy, że wyrocznie muszą używać spójnego i rozszerzalnego „kodowania” swoich danych wejściowych.
Następnie określa jeden jednolity rodziny obwodu, gdzie bramy oracle należą dopuszczalnych operacji do obwodu ograniczającego obwód wielkości wejściowej n użyć bramy O _n .

Wyobrażam sobie, że niektóre z powyższych wyborów mogą być arbitralnie ustalone bez utraty ogólności. Interesuje mnie odniesienie do korespondencji lub przynajmniej opis sposobu modyfikacji powyższego opisu w celu uzyskania standardowego.

cc.complexity-theory turing-machines oracles circuit-families Niel de Beaudrap
źródło

Ponieważ wiem, że pracujesz w informacji kwantowej, poleciłbym ankietę Johna Watrousa na temat złożoności obliczeniowej kwantowej, w której mówi on również o wyroczniach w obwodach kwantowych i pytaniu o wyrocznię w superpozycji.

Robin Kothari,

Dobry artykuł stanowi również artykuł Watrous. Ale okazało się, że w tym przypadku potrzebowałem, aby w jakiś sposób nie wierzyć, że ktoś chciałby zdefiniować relatywizowaną rodzinę obwodów w sposób, który nie odpowiadałby jedynie testowaniu tego samego predykatu dla różnych długości łańcucha, ponieważ przypomniał, że semantyka wyroczni klasycznie ma oznaczać członkostwo w jakimś zbiorze. Jak się okazało, rysunki bramek z symbolami „∈A?” na nich było wszystko, czego potrzebowałem.

Niel de Beaudrap

Odpowiedzi:

Najlepszym odniesieniem dla relatywizowanych obwodów jest artykuł Chrisa Wilsona „Relativized NC” http://www.springerlink.com/content/u727654246wu8662/

Drugi warunek (zamknięcie O_n w dół) nie jest potrzebny do uzyskania równoważności między P ^ O a jednorodnymi obwodami wielowymiarowymi z oracle O. Również trzeci warunek powinien zostać wyrzucony, rozmiar obwodu uniemożliwi dostęp do O_m dla m większy niż rozmiar obwodu.

Lance Fortnow
źródło

W artykule Wilsona nie ma wyraźnego komentarza na temat samych bram wyroczni; ale z perspektywy czasu, jeśli poważnie traktujecie wyrocznię jako reprezentującą przynależność do zestawu łańcuchów boolowskich, tak jak w przypadku TM, to mój drugi warunek jest po prostu nieistotny (tzn. jest oczywisty). Obserwując zbędność mojego trzeciego warunku, wystarczy mieć nieskończoną rodzinę bram, które decydują o członkostwie w A dla dowolnego określonego rozmiaru łańcucha. To działa dla mnie; Chciałbym o tym pomyśleć.

Niel de Beaudrap,

Uwagi na korzyść przypadkowych widzów --- artykuł Wilsona określa głębokość wkładu wyroczni na k bitów jako pułap (log k), w sposób analogiczny do wcześniejszej pracy Cooka („Taksonomia problemów z szybkimi algorytmami równoległymi” , Inform. And Control, 64). Istnieje kwestia techniczna, czy zezwalać na zapytania Oracle w trakcie budowy samych obwodów (z których każdy może również używać Oracle): komentuje, że nie ma to znaczenia. Ostatecznie jednak jest niezadowolony z istnienia A, dla którego NC_1 ^ A nie jest zawarte w NSPACE ^ A (O (n ^ k)), dla dowolnej stałej k.

Niel de Beaudrap,