Beziehung zwischen NP-harten und unentscheidbaren Problemen

Question

Bin ein bisschen verwirrt über die Beziehung zwischen unentscheidbaren Problemen und NP harten Problemen. Ob NP schwere Probleme eine Untermenge von unentscheidbaren Problemen sind, oder sind sie gleich und gleich, oder sind sie nicht vergleichbar?

Für mich habe ich mit meinen Freunden gestritten, dass unentscheidbare Probleme ein Superset zu den NP schweren Problemen sind. Es würde einige Probleme geben, die nicht in NP schwer sind, aber unentscheidbar sind. Aber ich finde dieses Argument schwach und bin ein wenig verwirrt. Gibt es NP-vollständige Probleme, die unentscheidbar sind? Gibt es irgendein Problem in NP hart, das entscheidbar ist?

Eine Diskussion wäre sehr hilfreich! Vielen Dank!

Answer 1

Unentscheidbar = für einige Eingaben nicht lösbar. Egal wie viel (endliche) Zeit Sie Ihrem Algorithmus geben, es wird bei einigen Eingaben immer falsch sein.

NP-hart ~ = Super-Polynom-Laufzeit (unter der Annahme, dass P! = NP). Das ist hand-wellig, aber im Grunde NP-hart bedeutet es mindestens so schwer wie das schwierigste Problem in NP.

Es gibt sicherlich Probleme, die NP-schwer sind, die nicht unentscheidbar sind (= entscheidbar sind). Jedes NP-vollständige Problem wäre einer von ihnen, sagen wir SAT.

Gibt es unentscheidbare Probleme, die nicht NP-schwer sind? Ich denke nicht, aber es ist nicht leicht, es auszuschließen - ich sehe kein offensichtliches Argument, dass es eine Reduzierung von SAT zu allen möglichen unentscheidbaren Problemen geben muss. Es könnte einige seltsame unentscheidbare Probleme geben, die nicht sehr nützlich sind. Aber die standardmäßigen unentscheidbaren Probleme (z. B. das Halteproblem) sind NP-schwer.

Answer 2

Ein NP-hart ist ein Problem, das mindestens so schwer wie jedes NP-vollständige Problem ist.

Daher kann ein unentscheidbares Problem NP-schwer sein. Ein Problem ist NP-schwer, wenn ein Orakel dafür NP-vollständige Probleme leicht lösen würde (d. H. In polynomieller Zeit lösbar). Wir können uns ein unentscheidbares Problem vorstellen, so dass NP-vollständige Probleme bei einem gegebenen Orakel leicht zu lösen wären. Zum Beispiel kann offensichtlich alle Orakel, die das Halteproblem löst, auch ein NP-vollständiges Problem lösen, so dass jedes Turing-vollständige Problem auch NP-schwer in dem Sinne ist, dass ein (schnelles) Orakel dafür NP-vollständig lösen würde Probleme ein Kinderspiel.

Daher Turing-komplette unentscheidbare Probleme sind eine Untergruppe der NP-harten Probleme.

Answer 3

Unentscheidbares Problem, z.B. Turing-Halteproblem ist nur NP-Hard.

    <---------NP Hard------> 
|------------|-------------||-------------|------------|--------> Computational Difficulty 

|<----P--->| 

|<----------NP---------->| 

|<-----------Exponential----------->| 

|<---------------R (Finite Time)---------------->| 

In diesem Diagramm, dass kleine Rohr aus NP und NP-Hard Überlappung zeigt und die zeigt, NP-Vollständigkeits, d.h. Menge derjenigen Probleme, die NP als auch NP-hart sind.

Unentscheidbare Probleme sind NP Hard Probleme, die keine Lösung haben und die nicht in NP sind.