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.
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.P A P A N P 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 .
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 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 .
Odpowiedzi:
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.PA NPA A NPA A A PA
źródło