Wie können wir wissen, dass NP-vollständige Probleme am schwierigsten in NP sind?

Question

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?

Answer 1

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.

Answer 2

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).

Answer 3

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.