Muss ein NP-hartes Problem berechenbar sein?
Das glaube ich nicht, aber ich bin mir nicht sicher.
quelle
Muss ein NP-hartes Problem berechenbar sein?
Das glaube ich nicht, aber ich bin mir nicht sicher.
Nein, ein -hard Problem muss nicht berechenbar sein. Die Definition ist ziemlich vollständig: Ein Problem ist -hart, wenn dieses Problem mit einer Mehrfachzeitlösung impliziert, dass jedes Problem in eine Mehrfachzeitlösung hat ( dh für jedes Problem in N P existiert eine Reduktion auf .).
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 -Problem gibt, das wir betrachten.
Betrachten wir zum Beispiel das Halteproblem . Wir können jede N P Sprache A auf reduzierenwie folgt H, vorausgesetzt, wir haben einen Polytime-Checker f ( s , c ), der prüft, ob c ein Zertifikat für s ∈ A ist :
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.
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.
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.
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:
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.H H H H
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önnenB A⊕B A⊕B A B A⊕B A A⊕B : Ä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 BA⊕B A⊕B B 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≠ Π01 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ösenA A . 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önnenA A 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.)Π01
quelle
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:
Jeder weiß, dass das nicht berechenbar ist
quelle
problem()
Wir können keine Funktion aufrufen.Der Vollständigkeit halber wollen wir folgenden Satz beweisen:
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 ?≠ Ti L {0,1,?} {0,1}∗ L 0 L 1 L , 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 )2i Ti Ti Ti x L(x)=? L(x):=0 Ti(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+1 Ti Ti Ti x L(Ti(x))=? x∈SAT x codiert einen erfüllbaren CNF), dann setzen wir , und andernfalls setzen wir L ( x ) : = 1 .L(x):=0 L(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 +L 2i Ti Ti L Ti Ti L Ti ≠ Ti 2i+1 schließt eine Reduzierung von SAT auf .L
quelle
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 TuringmaschinenL L′∈NP L′ L
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 durchL′∈NP L′ M′ f L′ ANTM
quelle
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.
LetA 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 ofA and is denoted by A′ .
So A<A′ strictly.
And nothing stops us from repeating this:
A<A′<A′′<A′′′<...
quelle