Czy można ustalić, czy język L leży w NP?

Biorąc pod uwagę język L zdefiniowany przez maszynę Turinga, która go decyduje, czy możliwe jest algorytmiczne określenie, czy L leży w NP?

Nie. Po pierwsze, według twierdzenia Rice'a, jest to właściwość baz TM, która zależy tylko od języka, który obliczają, więc nie może być obliczalna.

Ale, co więcej, wiadomo, że zbiór indeks (czyli zbiór baz że języki obliczeniowe w N P ) jest Σ 0 3 -Complete ( Σ 0 3 w arytmetycznej hierarchii obliczalności, a nie hierarchia wielomianowa).$NP$$NP$$\Sigma^0_3$$\Sigma^0_3$

Takie pytania zostały po raz pierwszy zbadane przez Hajeka . Więcej informacji można znaleźć np. W tym artykule Kena Regana.

Kilka innych samorodków z gazety Hajeka:

• Zestaw wskaźników wynosi Σ 0 3 - kompletny.$P$$\Sigma^0_3$
• ma wartość Π 0 2 -kompletną$\{i : P^{L(M_i)} \neq NP^{L(M_i)}\}$$\Pi^0_2$
• Istnieje całkowita maszyna Turinga (zatrzymuje się na wszystkich wejściach) taka, że P L i = N P L i ale wyrażenie „ P L i = N P L $M_i$$P^{L_i} = NP^{L_i}$$P^{L_i} = NP^{L_i}$ ” jest niezależne (gdzie ) . Podobnie dla relativizations gdzie P ≠ N P .$L_i = L(M_i)$$P \neq NP$

Odpowiedź na twoje dosłowne pytanie brzmi „nie”, jak zauważył Joshua Grochow.

Jednak, jak stwierdził Holger, możliwe jest sprawdzenie w czasie liniowym, czy niedeterministyczna maszyna Turinga (NTM) „sam się taktuje” i zatrzymuje po krokach n ^ k dla pewnego stałego k, za pomocą standardowego sposobu symulowania zegara (takiego jak kod poniżej). Często, gdy artykuł lub książka sugeruje (niepoprawnie), że możliwe jest ustalenie, czy NTM jest czasem wielomianowym, właśnie to mają na myśli. Być może dlatego zadałeś pytanie? (Miałem to samo pytanie, kiedy po raz pierwszy nauczyłem się teorii złożoności i gdzieś zobaczyłem stwierdzenie, że można sprawdzić, czy TM jest wieloczasowe). Prawdziwe pytanie brzmi: dlaczego ktoś może chcieć to zrobić, o czym dyskutuję poniżej po wyjaśnieniu w jaki sposób .

Istnieje wiele sposobów dodawania takiej funkcji zegara. Na przykład, wyobraź sobie na wejściu x o długości n, naprzemiennie wykonując jedną instrukcję taktowania „algorytmu głównego”, a następnie jedną instrukcję następującego algorytmu, która kończy się (coś bliskiego) n ^ k krokami:

dla i_1 = 1 do n
  dla i_2 = 1 do n
...
        dla i_k = 1 do n
          brak operacji;
powrót;

Jeśli powyższy kod powróci, zanim algorytm główny zatrzyma się, zatrzymaj całe obliczenia (powiedzmy z odrzuceniem).

Algorytm decydujący o tym, czy NTM ma taką postać, jeśli zostanie zinterpretowany jako próba algorytmu decydującego, czy jego dane wejściowe są wielozadaniowym NTM, zgłosi pewne fałszywe negatywy: niektóre NTM mają zagwarantowane zatrzymanie w czasie wielomianowym, mimo że nie naprzemiennie wykonują jedną instrukcję algorytmu z jedną instrukcją zegara, tak jak powyższy kod (stąd zostałby odrzucony, mimo że byłby wieloczasowy).

Ale nie ma fałszywych trafień. Jeśli NTM przejdzie test, to na pewno zatrzyma się w czasie wielomianowym, stąd definiuje jakiś język NP. Być może zachowanie pierwotnego algorytmu podstawowego ulegnie zmianie, jeśli zegar czasami skończy się, zanim zatrzyma się główny algorytm, co spowoduje odrzucenie obliczeń, nawet jeśli algorytm pierwotny może zaakceptować, jeśli otrzyma wystarczającą ilość czasu na zakończenie. Dlatego wybrany język może być inny niż algorytmu podstawowego. Ale, i to jest klucz, jeśli wykonywany algorytm pierwotny jest w rzeczywistości algorytmem czasu wielomianowego działającym w czasie p (n), a jeśli stała k w zegarze jest wystarczająco duża, aby n ^ k> p (n), to główny algorytm zawsze się zatrzyma, zanim skończy się zegar. W tym przypadku odpowiedź pierwotnego algorytmu nie jest zmieniana, więc algorytm pierwotny i taktowany NTM symulujący go decydują zatem o tym samym języku NP.

Dlaczego to jest ważne? Oznacza to, że możliwe jest „wyliczenie wszystkich języków NP” (co, jak powiedziałem, w literaturze jest często niedokładne, stwierdzone jako „zdecyduj, czy dany NTM jest wielogodzinny” lub „wyliczyć wszystkie wielogodzinne NTM”). Dokładniej, możliwe jest wyliczenie nieskończonej listy NTM M_1 M_2, ..., o właściwościach, które

1. Każdy M_k działa w czasie wielomianowym (na przykład, dołączając zegar ^ k-time do M_k), stąd decyduje się na jakiś język NP, i
2. Każdy język NP jest językiem ustalonym przez niektórych M_i na liście.

Nie dzieje się tak, że każdy NTM w czasie wielomianowym znajduje się na liście. Ale każdy język NP ma nieskończoną liczbę reprezentujących go NTM. Zatem każdy język NP ma zagwarantowane, że ma przynajmniej kilka reprezentatywnych NTM na liście, w szczególności wszystkie te NTM o wystarczająco dużym indeksie k, że n ^ k przekracza czas działania M_k.

Jest to przydatne do wykonywania sztuczek takich jak diagonalizacja, które wymagają algorytmicznego wyliczania takich nieskończonych (lub nieograniczonych) list wszystkich języków NP. Oczywiście cała ta dyskusja dotyczy wielu innych rodzajów maszyn oprócz wielozadaniowych wielozadaniowych maszyn NTM, takich jak deterministyczne wielozadaniowe bazy TM.

$p(n)$