Intuicja stojąca za relatywizacją

10

Biorę kurs na złożoność obliczeniową. Mój problem polega na tym, że nie rozumiem metody relatywizacji . Próbowałem znaleźć odrobinę intuicji w wielu podręcznikach, jak dotąd niestety bez powodzenia. Będę wdzięczny, jeśli ktoś może rzucić światło na ten temat, abym mógł kontynuować sam. Kilka kolejnych zdań to pytania, a moje przemyślenia na temat relatywizacji pomogą w prowadzeniu dyskusji.

Bardzo często relatywizacja występuje w porównaniu z diagonalizacją, która jest metodą, która pomaga odróżnić zbiór policzalny od zbioru niepoliczalnego. Z relatywizacji wynika, że pytania kontra N P nie da się rozwiązać za pomocą diagonalizacji. Nie bardzo rozumiem, dlaczego relatywizacja pokazuje bezużyteczność diagonalizacji, a jeśli jest bezużyteczna, to dlaczego jest bezużyteczna.PNP

Idea stojąca za wyrocznią maszyny Turinga na początku jest bardzo jasna. Jednak jeśli chodzi o i intuicja znika. Oracle to czarna skrzynka, która została zaprojektowana dla specjalnego języka i odpowiada na pytanie, czy ciąg znaków na wejściu wyroczni jest w języku w czasie 1. Jak zrozumiałem, TM zawierająca wyrocznię wykonuje tylko operacje pomocnicze i pyta wyrocznię. Tak więc rdzeniem TM jest wyrocznia, wszystko inne jest mniej ważne. Jaka jest różnica między i , nawet myśl, że wyrocznia w obu z nich działa w czasie 1.MAP A P A N P ANPAPAPANPA

Ostatnią rzeczą jest udowodnienie istnienia wyrocznią takie, że P BN P B . Znalazłem dowód w kilku podręcznikach i we wszystkich z nich dowód wydaje się bardzo niejasny. Próbowałem użyć „Wstępu do złożoności” Sipsera, rozdział 9. Krnąbrność i nie dostać się pomysł budowy listy wszystkich czasie wielomianowym TM oracle M I .BPBNPBMi

To mniej więcej wszystko, co wiem o relatywizacji, docenię, jeśli ktoś zdecyduje się podzielić swoimi przemyśleniami na ten temat.

Dodatek : w jednym z podręczników znalazłem przykład języka (Złożoność obliczeniowa: nowoczesne podejście Boaza Baraka Sanjeeva Arory. Twierdzenie 3.7. Strona 74). U B = { 1 n : s o m e s t r i n g o f l e n g t h n i s i n B } to jednoargumentowy język. Wierzę, że (1,11,111,1111, ...) są w U B . Autor potwierdza, że ​​taki język jest w językuNPBUB={1n:some string of length n is in B}UB czyli nie rozumiem dlaczego, dlatego wyrocznia dla B może rozwiązać wszystko na czas 1. Dlaczego potrzebujemy niedeterministycznej TM z wyrocznią. Jeśli to nie jest dobry przykład N P B proszę umieścić je w taki sposób, aby zatwierdzić istnienie N P B .NPBNPBNPB

com
źródło
2
i N P A są klasami języka, nie są maszynami Turinga. Mówicie, że wyrocznia jest „rdzeniem” TM, ale niekoniecznie jest to prawdą. Na przykład, co jeśli A jest pustym językiem? P.ZAN.P.ZAZA
Yuval Filmus
jest to bardzo trudny temat na ogół nie tyle dla studentów. jednym z aspektów jest to, że wyrocznie są w pewnym stopniu zależne od modelu. tzn. najwyraźniej nie ma ściśle spójnego sposobu wymyślania wyroczni. podstawowa intuicja polega na tym, że jest to maszyna z „magiczną” funkcją podprogramu (podaną przez wyrocznię), dzięki czemu maszyna + wyrocznia jest zawsze co najmniej tak potężna jak oryginalna maszyna, ale czasami nie jest znacznie mocniejsza…
vzn
1
powiązane pytanie: cs.stackexchange.com/questions/1271/... , ze świetną odpowiedzią Tsuyoshi Ito
A.Schulz
Nie jestem pewien, o co pytasz. Wygląda na to, że jesteś zdezorientowany co do dowodu BGS i zadajesz wiele innych pytań. Zadaj jedno ukierunkowane pytanie. Pamiętaj, że nie jest to forum dyskusyjne ani forum, to strona z pytaniami i odpowiedziami.
Kaveh
Czy prosisz o wyjaśnienie dowodu BGS na istnienie wyroczni, która oddziela P i NP? Czy pytasz o wyjaśnienie dotyczące relacji relatywizacji i diagonalizacji? (jeśli tak, to czy odpowiedź Tsuyoshi w zadanym pytaniu odpowiada na twoje pytanie? jeśli nie, proszę wyjaśnij, dlaczego nie.)
Kaveh,

Odpowiedzi:

7

Ty naprawdę nie zapytany, ale wydaje się, że nie wiem, co oznacza i co N P A środki na język A . Klasa N P A to po prostu wszystkie języki, które można rozstrzygać w „czasie NP”, biorąc pod uwagę maszynę Turinga z A jako wyrocznią. Oznacza to niedeterministyczną maszynę Turinga z dostępem do A, która działa w czasie wielomianowym. P jest wersja deterministyczny.PANPAANPAAAPA

Pål GD
źródło
1
Bardzo dziękuję za odpowiedź, czy możesz podać przykład, w jaki sposób moc NTM z oracle pomaga nam rozpoznać więcej języków niż DTM z oracle. Dowód BGS pokazuje taki język, ale nie dostałem dowodu.
com
APNPAA
PNPP