Gibt es ein NP Beispiel, dass wir eine Antwort in Polynomzeit bekommen

Question

Ich lese NP und P nur auf wikipedia, ich habe zwei Fragen:

1. Können wir ein NP Beispiel in Polynomialzeit lösen?
2. Gibt es eine NP Beispiel, das wir eine Antwort in Polynomzeit bekommen

Answer 1

Haftungsausschluss: Diese Antwort auf die praktischen Aspekte konzentriert sich mit der Tatsache zu tun, dass es Probleme gibt, für die kein Algorithmus Polynom-Zeit ist bekannt. Um eine theoretisch genaue Antwort zu geben, ist die in der Frage verwendete Terminologie nicht klar genug.

Es gibt zwei Bedeutungen von NP in der Informatik, die leicht durcheinander gebracht werden können.

(1) NP als die Klasse NP vollständigen Probleme:

Für keines dieser Probleme ein Polynom-Algorithmus bisher gefunden wurde. Es wurde bewiesen, dass, wenn ein solcher Algorithmus für eines dieser Probleme gefunden wird, jeder von ihnen in polynomieller Zeit gelöst werden kann. Das Standardbeispiel für die NP-Vollständigkeit ist das Problem des Traveling Salesman.

(2) NP als Eigenschaft eines Algorithmus, erfordert exponentielle Zeit:

Jeder NP-Algorithmus kann für kleine Größen gelöst werden N. Die Frage ist nur, dass die Anzahl der Berechnungen exponentiell zunimmt (dh sehr schnell) mit N.

Es gibt Probleme, für die ursprünglich nur NP-Algorithmen bekannt waren, für die aber später polynomielle Zeitalgorithmen gefunden wurden. Leider kann ich momentan kein Beispiel finden.

Für viele Probleme, die nur NP-Lösungen haben, gibt es polynomielle Zeitalgorithmen, die gute Annäherungen an die optimalen Lösungen liefern. Für viele Anwendungen ist dies ausreichend.