Intuicja stojąca za relatywizacją

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.$P$$NP$

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.$M^A$P A P A N P $NP^A$$P^A$$P^A$$NP^A$

Ostatnią rzeczą jest udowodnienie istnienia wyrocznią takie, że P B ≠ N 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 .$B$$P^B \neq NP^B$$M_i$

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ęzyku$NP^B$$U_B=\left \{ 1^n:some \space string \space of \space length \space n \space is \space in \space B\right \}$$U_B$ 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 .$NP^B$$NP^B$$NP^B$

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.$\rm{P}^A$$\rm{NP}^A$$A$$\rm{NP}^A$$A$$A$$\rm{P}^A$