NP-trudne problemy, które nie są NP-kompletne są trudniejsze?

Question

Z mojego rozumienia, wszystkie problemy NP-zupełne są NP-trudne, ale niektóre problemy NP-trudne nie są NP-zupełne, a NP-trudne problemy są co najmniej tak trudne, jak problemy NP-zupełne.

Czy to znaczy, że problemy NP-trudne, które nie są NP-kompletne, są trudniejsze? I jak to jest trudniejsze?

Answer 1

Od http://en.wikipedia.org/wiki/NP-hard#Examples

Istnieją również problemy decyzyjne, które są NP-trudne, ale nie NP-zupełny, na przykład powstrzymanie problem. To jest problem, który pyta "dany program i jego wkład, czy będzie działać wiecznie?" To jest pytanie "tak/nie", więc jest to problem z decyzją. Łatwo jest udowodnić, że problem z zatrzymaniem jest NP-trudny, ale nie NP-zupełny.

Answer 2

Zestaw problemów NP-trudnych jest nadzbiorem zestawu problemów NP-zupełnych. Istnieją klasy złożoności bardziej "trudne" niż NP, na przykład PSPACE, EXPTIME lub EXPSPACE, a wszystkie one zawierają problemy NP-trudne, ale nie NP-zupełne.

Answer 3

Aby odpowiedzieć na to pytanie, najpierw trzeba zrozumieć, które problemy NP są również NP-zupełne. Jeśli problem NP jest trudny do ustawienia NP, to jest NP-zupełny. Aby należeć do ustawienia NP, problem musi być

(i) problem decyzyjny,
(ii) liczbę rozwiązań tego problemu powinno być skończone i każde rozwiązanie powinno być długości wielomianu i
(iii) biorąc pod uwagę rozwiązanie wielomianowej długości, powinniśmy być w stanie powiedzieć, czy odpowiedź na problem jest tak/nie

Teraz łatwo zauważyć, że może być wiele problemów NP-trudnych, które nie należą do zestawu NP i są trudniejsze do rozwiązania. Jako intuicyjny przykład, wersja optymalizacyjna podróżującego sprzedawcy, w której musimy znaleźć rzeczywisty harmonogram, jest trudniejsza niż wersja decyzji podróżującego sprzedawcy, w której musimy ustalić, czy harmonogram o długości < = k istnieje, czy nie.

Answer 4

Problem z zatrzymaniem maszyny Turinga jest nierozstrzygalny w maszynach Turinga i NP-twardych, ale nie w NPC. Wygląda na to, że jest trudniej;)

Answer 5

Problem z zatrzymaniem Turinga jest nierozstrzygalny i należy do zestawu NP-Hard. W przypadku problemu z zatrzymaniem nie mamy żadnego decydującego, ponieważ jest to język RE. Nie mamy więc żadnego algorytmu, aby go rozwiązać. Oczywiste jest więc, że nierozwiązywalne problemy występują również w zestawie NP-Hard. Zestaw NP-Hard zawiera również języki lub problemy, dla których nie mamy żadnego algorytmu do rozwiązania.

Answer 6

1. NP-complete musi być NP i NP-trudny.
2. i NP-hard, które nie są NP-kompletne, nie są NP.
3. Teraz z definicji NP jest ktoś, kto daje instancji odpowiedzi na problem. i jest weryfikator do zweryfikowania.
4. oznacza to, że NP-Hard nie ma żadnej z nich. Stąd są trudne do rozwiązania, to prawda.