Kann jemand bitte ein Beitragsbeispiel dafür geben?Wenn sich ein Problem in NP befindet, gibt es keinen bekannten Polynomzeitalgorithmus, um es zu lösen

Question

Gibt es einen bekannten Polynomzeitalgorithmus, um ein Problem zu lösen, das dieses Problem in NP befindet.Mir wurde gesagt, ist falsch, kann aber jetzt nicht an kein Beispiel vorstellen.

Answer 1

np ist die Klasse von Entscheidungsproblemen, bei denen jede Instanz mit einer Antwort "Ja" einen Beweis dafür hat, dass die Antwort ja ist, der in der Polynomzeit überprüft werden kann.NP enthält alle Probleme, die bei der Polynomialzeit lösbar sind.Daher gibt es viele Probleme in NP mit bekannten Polynomzeitalgorithmen.

Wenn Sie über NP-vollständige Probleme sprechen, ist das eine ganz andere Angelegenheit.Es gibt (zu diesem Zeitpunkt) kein NP-vollständige Problem mit einem bekannten Polynomzeitalgorithmus, um es zu lösen.

0

Auf der anderen Seite kann jemand tatsächlich eine NP-Komplettierung finden, die in der Polynomzeit gelöst werden kann.Es ist jedoch unwahrscheinlich.