P, NP i specjalistyczne maszyny Turinga

Jestem w pewnym sensie nowy, ale bardzo zainteresowany dziedziną obliczeń i teorii złożoności, i chcę wyjaśnić moje rozumienie, w jaki sposób klasyfikować problemy i jak silnie problemy odnoszą się do maszyny używanej do ich rozwiązywania.

Moje zrozumienie

• Standardowa maszyna Turinga - maszyna Turinga, która ma skończony alfabet, skończoną liczbę stanów i pojedynczą nieskończoną taśmę
• Maszyna równoważna Turinga - Maszyna Turinga, która może emulować i być emulowana przez Standardową Maszynę Turinga (dość często z pewnym kompromisem między przestrzenią a czasem osiągniętym przez emulację)
• P - klasa problemów, które można rozwiązać w czasie wielomianowym za pomocą standardowej maszyny Turinga (zdefiniowanej powyżej)
• NP - klasa problemów, które można zweryfikować w czasie wielomianowym za pomocą standardowej maszyny Turinga
• NP-complete- najtrudniejsze problemy, które wciąż występują NP, na które wszystkie NPproblemy można przekształcić w czasie wielomianowym

Moje pytanie

Są klasy złożoności ( P, NP, NP-completeitp) związanych z algorytmem, lub algorytmu i maszyny?

Mówiąc inaczej, jeśli możesz stworzyć Równoważną Maszynę Turinga (która może rozwiązać wszystkie problemy, które może zrobić Standardowa TM, ale w innym czasie / przestrzeni), a ta nowa maszyna mogłaby rozwiązać NP-completeproblem w czasie, który rośnie jako czy to sugerowałoby wielomian w odniesieniu do danych wejściowych P=NP?

A może NP-completeproblem musi zostać rozwiązany na wszystkich możliwych maszynach Turinga w czasie wielomianowym, aby można go było rozważyć P?

Czy też źle rozumiem coś fundamentalnego powyżej?

Spojrzałem (może nie z prawidłowymi wyszukiwanymi hasłami, nie znam całego żargonu), ale wydaje się, że większość wykładów / notatek itp. Koncentruje się na standardowych maszynach, ale mówi, że niestandardowe maszyny często mają trochę czasu / przestrzeni kosztem przestrzeni / czasu, nie mówiąc o tym, jak to wpływa na klasy złożoności. Nie jestem jeszcze wystarczająco zaznajomiony z żargonem w tej dziedzinie, aby znaleźć dokumenty, które to wyjaśniają.

Algorytmy i maszyny nie są zdefiniowane w twoim pytaniu i nie sądzę, że są potrzebne, aby zapytać o to, o co chcesz zapytać.

Klasy złożoności są definiowane za pomocą maszyn Turinga. To jest ich definicja. Jeśli chcesz coś udowodnić, musisz użyć tych definicji. Cokolwiek na temat jakiegokolwiek innego modelu nie jest powiązane, chyba że udowodnisz pewną zgodność między tym modelem a maszynami Turinga.

Dodajmy, że istnieje hipoteza, że ​​„wydajne” „obliczenia” w dowolnej „rozsądnej” „maszynie” przechwycą te same funkcje teoretyczne. Nie jest to jednak stwierdzenie możliwe do udowodnienia, chyba że zdefiniuje się cytowane warunki. Możemy to udowodnić dla wielu maszyn, ale nie dla wszystkich. Bycie ekwiwalentem maszyny Turinga nie jest wystarczające, chcemy, aby były tak silne , tj. Powinniśmy być w stanie symulować te maszyny za pomocą maszyn Turinga i odwrotnie. Fajna rzecz w iN P $\mathsf{P}$$\mathsf{NP}$jest to, że są to bardzo solidne klasy, tzn. małe i duże różnice w modelach maszyn nie zmieniają klasy. Jest to jednak prawdą przez cały czas. Na przykład mogę zdefiniować prosty nowy model obliczeń, w którym mam podstawową operację, która w stałym czasie rozwiązuje problem, który jest nierozwiązywalny w . Wtedy oczywiste jest, że ten model nie będzie silnie równoważny z maszynami Turinga.$\mathsf{P}$

Powyższy przykład był sztuczny. Jednak obecnie mamy model obliczeń, który wydaje się bliższy wydajnemu obliczeniu w praktyce niż maszyny Turinga w czasie wielomianowym: probabilistyczne / randomizowane maszyny Turinga z ograniczonym błędem , wydajne algorytmy w tym modelu są nazywane .$\mathsf{BPP}$

Wielu ekspertów uważa, że ale daleko nam do udowodnienia tego.$\mathsf{BPP}=\mathsf{P}$

Mamy inny model obliczeń, który niektórzy eksperci spodziewają się w praktyce: kwantowe maszyny Turinga, wydajne algorytmy w tym modelu są nazywane . Nie wiemy, czy różni się on od ale niektórzy eksperci przypuszczają, że jest on inny i ma większą moc niż .P $\mathsf{BQP}$$\mathsf{P}$$\mathsf{P}$

Krótko mówiąc, jeśli chcesz udowodnić wynik teorii złożoności na temat i , musisz użyć oryginalnych definicji za pomocą maszyn Turinga lub najpierw udowodnić zgodność między nimi a klasami, których używasz w oparciu o inny model obliczeń. Jak wspomniałem powyżej, dość łatwo jest tworzyć modele maszyn, w których wielomianowy „czas” w nich może rozwiązać problem (lub nawet dowolnie trudniejszy): wystarczy dodać podstawową operację do modelu maszyny, która rozwiązuje ten problem i niech „czas”, jaki zajmuje ta operacja, to jedna jednostka czasu.N P N $\mathsf{P}$$\mathsf{NP}$$\mathsf{NP}$

Wystarczy trywialna uwaga, aby podkreślić, że wydajna symulacja maszyny Turinga oznacza nie tylko, że może ona symulować obliczenia maszyny Turinga i vice versa skutecznie (spowolnienie wielomianowe czasu); ale także, że jego wejście / wyjście musi być skutecznie konwertowane z jednego modelu do drugiego.

Trywialny przykład: jeśli znajdziesz ekwiwalentne urządzenie Turinga, które może rozwiązać problem SAT w stałym czasie, ale używa jako danych wejściowych sterty kulek (jednoargumentowych), to nie możesz niczego wywnioskować. To samo, jeśli twoje urządzenie używa wejścia binarnego, ale wykonuje wykładniczą liczbę kroków w celu konwersji instancji SAT na używany przez nią format wejściowy .

Twoje zrozumienie jest bardzo dobre! Możesz również znaleźć więcej informacji w tekście, jeśli jesteś zainteresowany, np. Wprowadzenie Sipsera do teorii obliczeń.

Istnieje idea zwana Tezą Kościoła-Turinga, która mówi, że wszystko, co można jakoś obliczyć, można obliczyć za pomocą Maszyny Turinga. (Nie jest to możliwe do udowodnienia, ale tylko pomysł lub rodzaj prawa natury, które naszym zdaniem jest prawdą).

Wspominam o tym, ponieważ istnieje także „Rozszerzona teza Kościoła Turinga”, która mówi, że wszystko, co można obliczyć w czasie wielomianowym, można jakoś obliczyć w czasie wielomianowym za pomocą Maszyny Turinga.

Istnieje dobry powód, by wątpić w tę hipotezę, ponieważ znamy algorytmy obliczeń kwantowych, które uzyskują przyspieszenie lepsze niż wielomianowe w porównaniu do najbardziej znanych algorytmów klasycznych. Jednak poza tym uważa się, że każda klasyczna maszyna, którą można zbudować (z pewnością każdy wariant na maszynie Turinga) nie może być wykładniczo szybsza niż maszyna Turinga. Więc jeśli twoja „maszyna równoważna Turinga” mogłaby uruchomić algorytm, który rozwiązał problem NP-Complete w czasie wielomianowym, to P = NP, ponieważ mógłbym przekonwertować go na algorytm czasu wielomianowego dla tego samego problemu na TM.

Ale jeśli wymyślisz jakąś maszynę ekwiwalentną Turinga, prawdopodobnie jedną z pierwszych rzeczy, które zrobisz, jest wymyślenie, jak ją symulować za pomocą klasycznej TM, a to powie ci, czy masz konwersję w czasie wielomianowym lub nie. Odpowiedź prawie na pewno brzmi „tak”, z wyjątkiem tego, że może być on wykładniczo wolniejszy (ale nie szybszy - uważamy, że chyba nie jest to kwant).