Ist jedes NP-harte Problem berechenbar?

Antworten:

14

Nein, ein NP -hard Problem muss nicht berechenbar sein. Die Definition ist ziemlich vollständig: Ein Problem L ist NP -hart, wenn dieses Problem mit einer Mehrfachzeitlösung impliziert, dass jedes Problem in NP eine Mehrfachzeitlösung hat ( dh für jedes Problem in N P existiert eine Reduktion auf .).LNP

Unberechenbare Probleme sind dann schwer zu lösen: Nehmen wir an, wir könnten eines in polynomialer Zeit lösen. Dann verwenden wir den Beweis, dass es nicht berechenbar ist, um abzuleiten, dass es sowohl berechenbar als auch nicht berechenbar ist, ein Widerspruch. Aus dieser Unwahrheit können wir alles ableiten, nämlich, dass es einen polynomialen Zeitalgorithmus für jedes NP -Problem gibt, das wir betrachten.

Betrachten wir zum Beispiel das Halteproblem . Wir können jede N P Sprache A auf reduzierenHNPAwie folgt H, vorausgesetzt, wir haben einen Polytime-Checker f ( s , c ), der prüft, ob c ein Zertifikat für s A ist :Hf(s,c)csA

  • Eingegebene s
  • Baue (aber laufe nicht) Turing Machine die Eingabe x nimmt, versucht jedes Zertifikat c und hält an, wenn c ein Zertifikat ist, das bestätigt, dass s A ist .MxccsA
  • Rückgabe von (dh Rückgabe von true, wenn M bei Eingabe x anhält )H(M,x)Mx

Somit kann mit einem einzigen Aufruf zu einem Poly-Algorithmus des Halting Problem zu lösen, können wir jede lösen Problem in polynomialer Zeit.NP

Eine solche Reduzierung ist nicht sinnvoll, da nur gesagt wird, ob "wenn falsch, dann etwas". Wir wissen bereits, dass es keinen Polytime-Algorithmus für nicht berechenbare Probleme gibt.

jmite
quelle
7
"Die Definition ist ziemlich vollständig", folgt aber nicht diesem Zitat in Ihrer Antwort.
Ich habe eine Frage dazu. Ich kann mir eine Funktion vorstellen, die das Halteproblem für die größtmögliche Menge von Programmen unter bestimmten Einschränkungen löst, aber ich kann mir vorstellen, dass diese Funktion immer noch nicht berechenbar ist (in dem Sinne, dass wir sie selbst bei unendlich viel Zeit niemals finden würden). . Doch wenn wir irgendwie haben die Lösung für sie haben, ist es nicht einmal mir klar , dass es sollten alle NP-schwere Probleme unbedingt lösen. Entweder folgt die Logik in dieser Antwort nicht (dh unentscheidbar! = Nicht berechenbar), oder meine Argumentation ist fehlerhaft (wahrscheinlich). Also, was ist der Fehler?
Mehrdad
12
Der größte Teil dieser Antwort ist falsch, einschließlich Ihrer Definition von NP-schwer: Problem A ist NP-schwer, wenn "für jedes NP-Problem B eine Polyzeitreduktion von B auf A vorliegt". Das ist nicht dasselbe wie "Wenn A Polyzeit ist, dann ist P = NP." (Letzteres ist eine Konsequenz des ersteren, aber nicht umgekehrt.) Insbesondere gibt es mit ziemlicher Sicherheit nicht berechenbare Probleme, die auch nicht NP-hart sind. Ich habe die Details nicht ausgearbeitet, aber das Problem der Mitgliedschaft in einem ausreichend generischen Satz (im Sinne des Erzwingens) sollte den Trick tun. Das Stopp-Set ist jedoch durch Ihre Reduzierung NP-hart.
mlh
7
Stellen Sie sich eine Polyzeitreduktion von A nach B wie folgt vor: Es handelt sich um ein Programm, das in Polynomialzeit ausgeführt wird, aber die besondere Fähigkeit hat, in einem einzigen Schritt ein Orakel abzufragen, das die Fälle von Problem B beantwortet. Unabhängig davon, ob Es gibt einen Mehrfachzeitalgorithmus für B, oder auch wenn B berechenbar ist, ist es dennoch sinnvoll, die folgende Frage zu stellen: Unter der Annahme, dass das Orakel die gestellten Fragen richtig beantwortet (in einem einzigen Schritt), führt das betreffende Programm aus in polynomialer Zeit laufen und Instanzen von Problem A korrekt lösen?
mlh
2
@MikeHaskel Ihre Orakel-Analogie ist nur korrekt, wenn das Programm nach der Abfrage des Orakels mit derselben Antwort wie dieses Orakel anhalten muss. Andernfalls reduziert sich co-SAT auf SAT: Fragen Sie das Orakel ab und negieren Sie. In einigen Reduktionsbegriffen, z. B. der Turing-Reduktion, wäre dies akzeptabel, in der Standard-Polyzeitreduktion oder sogar in der Vielfachreduktion jedoch nicht.
Chi
16

In Bezug auf diese Frage scheint es in dieser Gemeinde einige erhebliche Verwirrung zu geben. Ich werde eine detaillierte Antwort geben, in der Hoffnung, das Wasser aufzuklären und die Beziehung zwischen Berechenbarkeit und NP-Härte zu beleuchten.

Erstens glaube ich, dass eine klare und eindeutige Darstellung der verschiedenen Definitionen viel Verwirrung beseitigen wird.

Eine Zeichenfolge ist eine endliche Folge von Zeichen aus einem festen endlichen Alphabet.

Ein Entscheidungsproblem ist eine Reihe von Zeichenfolgen. (Diese Menge ist normalerweise unendlich.) Stellen Sie sich das Entscheidungsproblem als Testen von Zeichenfolgen für eine Eigenschaft vor: Die Zeichenfolgen mit der Eigenschaft befinden sich in der Menge, und die Zeichenfolgen ohne die Eigenschaft nicht.

Angenommen , wir haben zwei Entscheidungsprobleme, und B . Sagen wir, A ist polynomial-zeitreduzierbar auf B, wenn es ein Polynom p ( x ) gibt, und einen Algorithmus M , der für alle Zeichenfolgen giltABABp(x)M ,s

  • Wenn Sie mit Eingaben s versehen , stoppt M in weniger als p ( | s | ) Schritten (wobei | s | die Länge der Zeichenfolge s ist ) und gibt eine Zeichenfolge M ( s ) aus .MsMp(|s|)|s|sM(s)
  • istgenau dannin A, wenn M ( s ) in B ist .sAM(s)B

Ein Entscheidungsproblem ist NP-hart , wenn für jedes NP Entscheidungsproblem A , A Polynom-Zeit reduzierbar ist B .BAAB

Ein Entscheidungsproblem ist berechenbar, wenn es für alle Zeichenketten einen Algorithmus gibtM ,s

  • Wenn Sie bieten mit Eingabe s ,Ms stoppt und gibt entweder „Ja“ oder „Nein“.M
  • Die Ausgabe ist "yes", wenn ists und "nicht.A

Mit den obigen Definitionen können wir sofort klarstellen, was meiner Meinung nach die Grundverwirrung in Ihrer Frage sein könnte: Nichts in den Definitionen von Entscheidungsproblemen, Reduktionen oder NP-Härte erfordert, dass die Entscheidungsprobleme berechenbar sind. Die Definitionen machen Sinn, wenn man Entscheidungsprobleme als willkürliche Mengen von Zeichenketten betrachtet, und diese Mengen können tatsächlich sehr unangenehm sein.


Damit bleiben zwei Fragen offen:

  1. Die Definitionen lassen die Möglichkeit offen, dass nicht berechenbare Funktionen NP-hart sein können. Gibt es eigentlich nicht berechenbare, NP-harte Funktionen?
  2. Es gibt eine Intuition, die besagt, dass es schwierig ist, ein Problem zu lösen. Zu sagen, dass es nicht berechenbar ist, ist wie zu sagen, dass es "wirklich schwer" zu lösen ist. So sind alle nicht berechenbaren Probleme NP-schwer?

Frage 1 ist einfacher zu beantworten. Es gibt zwei besonders wichtige Wege, um nicht berechenbare Entscheidungsprobleme zu finden, die NP-schwer sind. Das erste ist das Halteproblem: Das Halteproblem hat die Eigenschaft, dass jedes berechenbare Entscheidungsproblem in der Polynomzeit auf H reduzierbar ist . Da NP-Probleme berechenbar sind, ist jedes NP-Problem in der Polynomzeit auf H reduzierbar , so dass H NP-hart ist.HHHH

Der andere wichtige Weg, ein nicht berechenbares NP-hartes Problem zu erstellen, besteht darin, zu beobachten, dass wir jedes bekannte NP-hartes Problem mit jedem bekannten nicht berechenbaren Problem kombinieren können. Sei NP-hart undA nicht berechenbar. Bilden Sie das Entscheidungsproblem A B wie folgt: A B enthält die Zeichenfolgen der Form "0", gefolgt von einer Zeichenfolge in A "und dieZeichenfolgender Form" 1 ", gefolgt von einer Zeichenfolge in B ". A B ist NP-hart, weil wir jede Reduktion (von jedem Problem) auf A in eine Reduktion auf A B umwandeln könnenBABABABABAAB: Ändern Sie einfach den Algorithmus, um eine zusätzliche "0" am Anfang der Ausgabezeichenfolge auszugeben. ist nicht berechenbar, da für die Berechnung von A B entschieden werden muss, welche Zeichenfolgen, die mit "1" beginnen, in der Menge enthalten sind. das ist unmöglich, da BABABB nicht berechenbar ist.


Frage 2 ist erheblich schwieriger, aber tatsächlich gibt es nicht berechenbare Entscheidungsprobleme, die nicht NP-hart sind (unter der Annahme von P NP). Yuvals feine Antwort konstruiert ein solches Entscheidungsproblem explizit. (Für alle Rechnbarkeitstheoretiker im Raum kann jeder "Cohen Π 0 1Π10 Rechnbarkeitstheoretiker Generikum" den Trick machen.) Ich werde auf den Grund gehen, warum die Intuition, dass "NP-schwierige Probleme schwierig sind, nicht berechenbare Probleme schwieriger sind " ist falsch.

NP-Härte und Nicht-Berechenbarkeit besagen beide, dass ein Problem in einem sehr allgemeinen Sinne "hart" ist, aber sie sind sehr unterschiedlich und sollten nicht als die gleiche Art von Phänomen zusammengefasst werden. Insbesondere ist NP-Härte eine „positive“ Eigenschaft: ein NP-hard Problem ist schwer , in dem Sinne , dass, dem Zugang zu einem Spickzettel für A , Sie können eine harte Klasse von Problemen zu lösenAA . Auf der anderen Seite ist Nicht-Berechenbarkeit eine "negative" Eigenschaft: ein nicht berechenbares Problem schwer in dem Sinne, dass Sie A nicht lösen könnenAA mit einer bestimmten Klasse von Ressourcen können .

("Forcen" ist übrigens die Technik, mit der das von mir erwähnte "Cohen Generikum" hergestellt wird. Um sehr vage zu sein, ist Forcen eine allgemeine Methode, um Dinge zu erzeugen, die "generisch" sind Keine positiven Eigenschaften und jede negative Eigenschaft. Deshalb kann das Erzwingen direkt zu einem Problem führen, das weder berechenbar noch NP-hart ist.)Π10

mlh
quelle
2
Können Sie nicht eine unentscheidbare Sprache konstruieren, die durch Diagonalisierung nicht NP-hart ist? Diagonalisieren Sie gegen alle Entscheider und alle Polytime-Reduktionen von SAT.
Yuval Filmus
1
@YuvalFilmus Das funktioniert wahrscheinlich, ja. Ich denke, die Einzelheiten darüber, warum Diagonalisierung gegen Polytime Reductions von SAT-Mengen möglich ist, zu schreiben, ähnelt im Geschmack dem Zeigen, dass Forcen funktioniert, also habe ich in diesen Begriffen nicht darüber nachgedacht.
mlh
1
@YuvalFilmus Ich habe auch gerade die Klarstellung hinzugefügt, dass Sie P NP annehmen müssen : Es gab definitiv einen Schritt in meinem Beweis, der lautete: "Nimm ein Problem in NP, aber nicht in P."
mlh
1
@aelguindy Ich bin mir nicht sicher, welche Methode am einfachsten zu beweisen ist. Ich erwähnte die Technik des Erzwingens , die sehr allgemein und mächtig ist. Ich habe es von Menschen gelernt, nicht von Lehrbüchern, daher kenne ich persönlich keinen guten Hinweis auf das Forcen. Wie Yuval jedoch betonte, ist das Erzwingen wahrscheinlich übertrieben: Ein direkteres Argument bezüglich der Diagonalisierung funktioniert wahrscheinlich. Soares "Recursively Enumerable Sets and Degrees" ist ein Lehrbuch, das viele dieser Argumentationsstile behandelt, wenn Sie sich damit vertraut machen möchten. Auch hier ist das meiste wahrscheinlich übertrieben. ...
mlh
1
@aelguindy Wenn Sie sich die Menge der Entscheidungsprobleme als einen topologischen Raum vorstellen, können Sie wahrscheinlich den Satz der Baire-Kategorie massieren , um einen Beweis zu erhalten. Dieser Satz hängt eng mit dem Forcen zusammen, ist aber älter und unkomplizierter.
mlh
10

Nee. NP-Hard bedeutet, dass es genauso schwer oder schwerer ist als die schwierigsten NP-Probleme. Intuitiv wird es schwieriger sein, nicht berechenbar zu sein als NP.

Wikipedia:

Es gibt Entscheidungsprobleme, die NP-schwer, aber nicht NP-vollständig sind, zum Beispiel das Halteproblem.

Jeder weiß, dass das nicht berechenbar ist

Zerstörbare Zitrone
quelle
4
Beachten Sie, dass einige nicht berechenbare Probleme (wie das Stopp-Problem) NP-hart sind, dies jedoch nicht bedeutet, dass alle nicht berechenbaren Probleme NP-hart sind. Siehe meine Kommentare zu jmites Antwort. NP-Härte ist eine positive Eigenschaft: Er sagt , dass Antworten auf Ihr Problem kann helfen NP Probleme lösen. NP-schwer zu sein, bedeutet, dass das Problem bis zu einem gewissen Grad schwierig ist. Nicht alle schwierigen Probleme sind NP-schwer.
mlh
@ MikeHaskel: Wenn Sie die Lösung für das Halteproblem besitzen, werden alle Probleme auf die Schwierigkeit P * des Halteproblems reduziert.
Joshua,
1
@ Joshua: Das macht keinen Sinn. Es ist wie ein Fragment eines Nichtbeweises. Was meinen Sie eigentlich damit, dass ein Problem eine endliche Anzahl von Bits in seiner Lösung hat, und warum gilt dies Ihrer Meinung nach für alle nicht berechenbaren Probleme? Was meinst du mit "P * halts"? Was ist der Rest von "Reduzieren über das n-te Bit von ..."?
user2357112 unterstützt Monica
1
@Joshua: Sieht so aus, als ob das Kernproblem darin besteht, dass Sie davon ausgehen, dass jedes Problem einer Turing-Maschine entspricht. Nicht jedes Problem entspricht einer Turingmaschine. problem()Wir können keine Funktion aufrufen.
user2357112 unterstützt Monica
1
Sie sollten dies wahrscheinlich verschieben, um zu chatten oder etwas
Destructible Lemon
10

Der Vollständigkeit halber wollen wir folgenden Satz beweisen:

Es gibt eine nicht berechenbare Sprache, die genau dann nicht NP-hart ist, wenn P NP ist.

Wenn P = NP, dann jede nicht-triviale Sprache (eine, die sich von ,{0,1} ) NP-hart (Übung), und insbesondere ist jede nicht-berechenbare Sprache NP-hart.

Nehmen wir nun an, dass P NP. Sei T i eine Aufzählung aller Turingmaschinen. Wir werden die gewünschte Sprache L schrittweise konstruieren . In jeder Phase halten wir eine { 0 , 1 , ? } Färbung von { 0 , 1 } ∗, die wir auch mit L bezeichnen ; Hier bedeutet 0 , dass wir entschieden haben, dass die Zeichenfolge nicht in L ist. 1 , dass wir entschieden haben, dass die Zeichenfolge in L ist, bedeutet, dass wir uns noch nicht entschieden haben. Alle bis auf endlich viele Saiten werden gefärbt ?TiL{0,1,?}{0,1}L0L1L , und ??.

In Schritt wir uns T i als eine Maschine vor, die entweder ihre Eingabe akzeptiert, sie ablehnt oder niemals anhält. Wenn T i nicht immer halt dann tun wir nichts. Wenn T i Halt immer dann finden wir eine String x , so dass L ( x ) = ? und setze L ( x ) : = 0, wenn T i ( x ) akzeptiert und L ( x ) : = 1 ( x )2iTiTiTixL(x)=?L(x):=0Ti(x)L(x):=1 wenn iTi(x) lehnt ab.

In Schritt wir uns T i als eine Maschine vor, die eine (möglicherweise) Teilfunktion an ihrer Eingabe berechnet. Wenn T i nicht total ist oder wenn es total ist, aber nicht in Polynomzeit läuft, oder wenn es total ist, aber sein Bereich endlich ist, machen wir nichts. Wenn T i Insgesamt läuft in polynomialer Zeit ist, und unendliche Reichweite hat, dann finden wir eine String x , so dass L ( T i ( x ) ) = ? . Wenn x S A T ( dh wenn2i+1TiTiTixL(Ti(x))=?xSATxcodiert einen erfüllbaren CNF), dann setzen wir , und andernfalls setzen wir L ( x ) : = 1 .L(x):=0L(x):=1

Nach unendlich vielen Schritten, erhalten wir eine Färbung von { 0 , 1 } ∗, die wir auf beliebige Weise zu einer tatsächlichen Sprache vervollständigen.{0,1,?}{0,1}

Die resultierende Sprache ist nicht berechenbar: Schritt 2 i stellt sicher, dass T i es nicht berechnet. Es ist auch nicht NP-schwer, aber hier ist die Argumentation etwas heikler. Nehmen wir an, dass T i ist eine polytime Reduktion von SAT nach L . Wenn der Bereich von T i endlich ist, können wir T i in eine Polyzeitmaschine verwandeln, die über SAT entscheidet, indem wir die Wahrheitstabelle von L über den Bereich von T i auflisten . Dies ist unmöglich unter der Annahme P NP. Somit hat T i einen unendlichen Bereich, aber dann Schritt 2 +L2iTiTiLTiTiLTiTi2i+1 schließt eine Reduzierung von SAT auf .L

Yuval Filmus
quelle
3

Eine Sprache ist NP-schwer, wenn wir für jedes L 'N P haben, dass L ' in der Polynomzeit auf L reduzierbar ist . Das Akzeptanzproblem für nichtdeterministische TuringmaschinenLLNPLL

ANTM={M,wM is a nondeterministic Turing machine that accepts w}

ist unentscheidbar und NP-hart. Für eine prüfen . L ' wird von einer nichtdeterministischen Turingmaschine M ' mit polynomieller Zeitkomplexität bestimmt. Eine Polyzeitverkürzung f von L ' auf A N T M ist gegeben durchLNPLMfLANTM

f(x)=M,x
Hans Hüttel
quelle
3

Ich denke, was die Leute zu der Annahme veranlasst, dass es kein nicht berechenbares NP-hartes Problem gibt, ist, dass sie den Punkt übersehen, dass die NP-Härte eine Untergrenze für die Härte eines Problems ist und keine Obergrenze für ihre Härte wie P oder NP.

Eine Sprache L, die NP-hart ist, bedeutet, dass sie in NP über der Sprache liegt, und das ist. Wenn Sie dies verstehen, müssen Sie zeigen, dass es willkürlich schwierigere Probleme gibt.

Let A be a language. Consider algorithms augmented with a black-box that they can use to deciding membership in A. Let's denote them by CA. It is easy to see that the halting problem for CA, HaltCA is not in CA.

In computablity theory this is called jump of A and is denoted by A. So A<A strictly. And nothing stops us from repeating this: A<A<A<A<...

Kaveh
quelle