W jaki sposób problem sprzedawcy podróży jest weryfikowalny w czasie wielomianowym?

Rozumiem więc, że problem decyzyjny jest zdefiniowany jako

Czy istnieje ścieżka P taka, że koszt jest niższy niż C?

i możesz łatwo sprawdzić, czy to prawda, weryfikując otrzymaną ścieżkę.

Co jednak, jeśli nie ma ścieżki, która spełniałaby te kryteria? Jak zweryfikowałbyś odpowiedź „nie” bez rozwiązania problemu z najlepszą ścieżką TSP, a znalezienie najlepszego ma gorszy koszt niż C?

complexity-theory time-complexity np decision-problem traveling-salesman wjmccann
źródło

Osobiście słyszałem tylko, że klasa NP oznacza weryfikację w czasie wieloczasowym, ale nigdy nie widziałem ograniczenia, które oznacza jedynie weryfikację odpowiedzi „tak, oto rozwiązanie”. Wydaje się intuicyjne wyobrażenie sobie, że musisz być w stanie zweryfikować każde rozwiązanie w czasie wielozakresowym.

wjmccann

Odpowiedzi:

NP to klasa problemów, w których można zweryfikować wystąpienia „tak”. Nie ma gwarancji, że możesz zweryfikować instancje „nie”.

Klasą problemów, w których można zweryfikować instancje „nie” w czasie wielomianowym, jest ko-NP . Dowolny język w co-NP jest uzupełnieniem jakiegoś języka w NP i odwrotnie. Przykłady obejmują rzeczy takie jak brak 3-kolorowalności. Opisany problem: „Czy nie ma ścieżki TSP o długości co najwyżej ?” jest również w ko-NP : jeśli usuniesz podwójną negację, instancja „nie” dla tego problemu jest instancją „tak” dla TSP i możemy je zweryfikować w czasie wielomianowym. $C$

Istnieją pewne problemy, takie jak faktoryzacja liczb całkowitych i każdy problem w P , o których wiemy, że występują zarówno w NP, jak i w ko-NP . (Podziękowania dla user21820 za zwrócenie na to uwagi.)

Nie wiadomo, czy NP i co-NP to ten sam zestaw problemów. Jeśli są takie same, możemy zweryfikować zarówno „tak”, jak i „nie” wystąpienia TSP. Jeśli są różne, to P NP $\,\neq\,$ , ponieważ wiemy, że P co-P $\,=\,$ (ponieważ możemy po prostu zanegować odpowiedź maszyny deterministycznej, dając odpowiedź na problem uzupełnienia) .

David Richerby
źródło

Warto wspomnieć, że znamy niektóre problemy, które występują zarówno w NP, jak i coNP, ale nie wiemy, czy występują w P, czy nie, takie jak rozkład na czynniki całkowite.

user21820

@ user21820 Rozkład na czynniki całkowite nie stanowi problemu decyzyjnego. Pierwszeństwo jest problemem decyzyjnym i od lat wiadomo, że występuje zarówno w NP, jak i w NP . W końcu wykazano, że są w P również. I nie wiem, czy nadal istnieją problemy znane są zarówno w NP i współ-NP bez Wykazano, że w P .

kasperd

@kasperd: Jest dobrze znanym faktem, że faktoryzacja liczb całkowitych w przypadku problemu decyzyjnego (czy n ma czynnik pierwszy mniejszy niż m?) występuje zarówno w NP, jak i coNP (oba przypadki tak / nie można zweryfikować w czasie wielomianowym za pomocą test pierwszeństwa AKS, biorąc pod uwagę faktoryzację pierwszą jako certyfikat), ale nie został jeszcze pokazany jako P.

użytkownik21820

@ user21820 Istnieje wiele prostszych i szybszych sposobów weryfikacji faktoryzacji niż AKS.

kasperd

@kasperd: Byłbym ciekawy tutaj. Aby zweryfikować faktoryzację, potrzebujesz na przykład czynników pierwszych, a dla każdego czynnika pierwszego dowód, że jest liczbą pierwszą.

gnasher729

„W jaki sposób problem sprzedawcy podróży jest weryfikowalny w czasie wielomianowym?”

Albo w sposób, w jaki opisujesz, albo nie jest znany taki sposób.

„Co jednak, jeśli nie ma ścieżki, która spełniałaby te kryteria?”

W takim przypadku dla wszystkich maszyn NP dla problemu decyzyjnego maszyna zwróci nie dla wszystkich certyfikatów-kandydatów.

„Jak zweryfikowałbyś odpowiedź„ nie ”bez rozwiązania problemu z najlepszą ścieżką TSP, a znalezienie najlepszego ma gorszy koszt niż C?”

Cóż, można otrzymać interaktywny dowód, że nie ma takich ścieżek .

Opisany przez ciebie problem, TSP, nie jest znany z koNP , więc nie wiadomo, że istnieje „podobny do NP” sposób sprawdzenia, czy nie ma takiej ścieżki.

Juho
źródło