Ich bekomme, dass, wenn Sie eine polynomische Zeitreduktion von "jedem" Problem machen können, dann beweist es, dass das Problem mindestens so schwer wie jedes Problem in NP ist. Außer, woher wissen wir, dass wir jedes Problem in NP entdeckt haben? Kann es keine Probleme geben, die wir in NP vielleicht nicht entdeckt oder nachgewiesen haben, aber nicht auf ein NP-vollständiges Problem reduziert werden können? Oder ist das noch eine offene Frage?Wie können wir wissen, dass NP-vollständige Probleme am schwierigsten in NP sind?
Antwort
Wie andere korrekt festgestellt haben, würde die Existenz des Problems, das NP ist, aber nicht NP-vollständig ist, bedeuten, dass P! = NP, also würde man einen million dollar und ewigen Ruhm finden. Ein bekanntes Problem, von dem angenommen wird, dass es in diese Klasse gehört, ist integer factorization. Allerdings war Ihre ursprüngliche Frage
Kann nicht es Probleme gibt, die wir nicht in NP existieren entdeckt oder bewiesen haben, kann aber nicht an jedem NP-vollständiges Problem reduziert werden?
Die Antwort ist keine. Nach Definition der NP-Vollständigkeit ist eine der beiden notwendigen Bedingungen, dass ein Problem A NP-vollständig ist, dass jedes NP-Problem in polynomieller Zeit zu A reduzierbar sein muss. Wenn Sie herausfinden wollen, wie jeder einzelne NP zu beweisen ist Problem kann in polynomieller Zeit zu einem NP-vollständigen Problem reduzierbar sein, siehe den Beweis von Cook-Levin theorem, der besagt, dass das 3-SAT-Problem NP-vollständig ist.Es war das erste nachgewiesene NP-vollständige Problem, und viele andere NP-vollständige Probleme wurden später als NP-vollständig nachgewiesen, indem die geeignete Reduktion von 3-SAT auf diese Probleme gefunden wurde.
NP besteht aus allen Problemen, die (theoretisch) gelöst werden könnten, indem man glückliche Annahmen macht, die Lösung rät und die polynomielle Zeit eincheckt, dass die Lösung korrekt ist. Zum Beispiel kann das Problem des reisenden Verkäufers "kann ich die Kapitale aller 50 Staaten der USA mit einer Reise von weniger als 9.825 Meilen besuchen" gelöst werden, indem man eine Reise rät und überprüft, dass es nicht zu lange ist.
Und ein Problem in NP ist grundsätzlich eine programmierbare Computerschaltung mit verschiedenen Eingängen zu simulieren und zu überprüfen, ob eine bestimmte Ausgabe erreicht werden kann. Und diese programmierbare Computerschaltung ist stark genug, um alle Probleme in NP zu lösen.
Also ja, wir wissen alles über alle Probleme in NP.
(Dann natürlich ein NP vollständig Problem kann per Definition verwendet werden, um jedes Problem in NP zu lösen. Wenn es ein Problem gibt, dass es nicht lösen kann, ist dieses Problem nicht in NP).
Danke für Ihre Antwort. Warum ist es dann unmöglich, einen Algorithmus X zu finden, der in NP ist und ein NP-vollständiges Problem nicht auf X reduziert werden konnte? – rb612
@ rb612 Wenn ein Problem X in NP, aber nicht NP-vollständig ist, dann ist NP-Complete eine richtige Teilmenge von NP. Aber dann kann P nicht gleich NP sein, weil jedes Problem in P polynomial-zeitlich auf jedes andere Problem in P reduzierbar ist. Wenn also P = NP ist, müssen alle Probleme in NP NP-vollständig (dh in NP und polynomialer Zeit reduzierbar zu sein) sein gegenseitig). – Patrick87
Außer, woher wissen wir, dass wir jedes Problem in NP entdeckt haben?
Wir nicht. Die Menge aller Probleme im Universum ist nicht nur unendlich, sondern auch unzählbar.
Kann nicht existieren Probleme, die wir existieren in NP möglicherweise nicht entdeckt oder bewiesen, aber nicht zu jedem NP-vollständigen Problem reduziert werden?
Das wissen wir nicht. Wir vermuten, dass dies der Fall ist, aber dies ist noch nicht bewiesen. Wenn wir ein NP-Problem finden würden, das nicht in NP-Complete liegt, wäre dies ein Beweis dafür, dass P =/= NP.
Es ist eines der großen ungelösten Probleme in CS. Viele brillante Köpfe haben es versucht, aber diese Nuss war eine harte Nuss.
Das ist so interessant. Könnten Sie etwas mehr über das Auffinden eines NP-Problems erklären, das nicht NP-vollständig ist, wäre dies ein Beweis für P =/= NP? Weil ich dachte, der einzige Weg, um zu beweisen, dass P =/= NP ist, zu zeigen, dass kein Algorithmus jemals ein NP vollständiges Problem in der deterministischen Polynomzeit lösen könnte. – rb612
@ rb612 Wenn ein Problem X in NP, aber nicht NP-vollständig ist, dann ist NP-Complete eine richtige Teilmenge von NP. Aber dann kann P nicht gleich NP sein, weil jedes Problem in P polynomial-zeitlich auf jedes andere Problem in P reduzierbar ist. Wenn also P = NP ist, müssen alle Probleme in NP NP-vollständig (dh in NP und polynomialer Zeit reduzierbar zu sein) sein gegenseitig). – Patrick87
@ Patrick87 danke! Die akzeptierte Antwort besagt jedoch, dass alle Probleme in NP auf ein NP-vollständiges Problem reduziert werden können. Ist es schon bewiesen oder ist es noch unbekannt? Und können Sie mehr darüber ausarbeiten, was Sie mit "Dann kann P nicht NP gleichsetzen, weil jedes Problem in P ist polynomielle Zeit reduzierbar zu jedem anderen Problem in P." Ich sehe nicht, wie jedes Problem in P zueinander führt, dass P ≠ NP ist, wenn NP ⊂ NP-vollständig ist. – rb612
Danke! Die SAT-Idee macht es völlig sinnvoll. – rb612
@ rb612 Gern geschehen! –