NP-hardness

Euler diagram for P, NP, NP-complete, and NP-hard set of problems.
Euler -Diagramm zum P, Np, NP-Complete- und NP-harte Probleme. Die linke Seite ist unter der Annahme gültig, dass P ≠ npWährend die rechte Seite unter der Annahme gültig ist, dass P = NP (außer dass die leere Sprache und ihre Komplement niemals NP-Complete sind)

Im Computerkomplexitätstheorie, NP-Hardness (Nichtdeterministische Polynomzeit Härte) ist die definierende Eigenschaft einer Klasse von Problemen, die informell "zumindest so schwer wie die schwierigsten Probleme in Np". Ein einfaches Beispiel für ein NP-hartes Problem ist das Summenproblem.

Eine genauere Spezifikation ist: ein Problem H ist np-hard, wenn jedes Problem L In NP kann sein reduziert in Polynomzeit zu H; das heißt, eine Lösung für eine Lösung für H nimmt 1 Einheit Zeit, H'S -Lösung kann zur Lösung verwendet werden L in Polynomzeit.[1][2] Infolgedessen würde das Auffinden eines Polynomzeitalgorithmus zur Lösung eines NP-HART-Problems Polynomzeitalgorithmen für alle Probleme in NP geben. Wie vermutet wird, dass P ≠ npEs ist unwahrscheinlich, dass ein solcher Algorithmus existiert.[3]

Es wird vermutet, dass es keine Polynom-Zeit-Algorithmen für NP-HART-Probleme gibt, das jedoch nicht nachgewiesen wurde.[4] Darüber hinaus die Klasse P, in denen alle Probleme in der Polynomzeit gelöst werden können, ist in der enthalten Np Klasse.[5]

Definition

A Entscheidungsproblem H ist np-hard, wenn für jedes Problem L In NP gibt es a Polynomzeit viele eins Reduktion aus L zu H.[1]: 80 Eine äquivalente Definition besteht darin, dieses Problem zu verlangen L in NP kann in gelöst werden Polynomzeit durch eine Oracle Machine mit einem Orakel für H.[6] Informell kann ein Algorithmus angesehen werden, der eine solche Oracle -Maschine als Unterprogramm zum Lösen nennt H und löst L In der Polynomzeit, wenn der Unterroutine -Aufruf nur einen Schritt berechnet.

Eine andere Definition besteht darin, zu verlangen, dass es eine Polynomzeitreduktion von einem gibt NP-Complete Problem G zu H.[1]: 91 Wie jedes Problem L in NP reduziert sich in der Polynomzeit zu G, L reduziert sich wiederum auf H In der Polynomzeit impliziert diese neue Definition die vorherige. Untell Suchprobleme oder Optimierungsprobleme.

Konsequenzen

Wenn p ≠ np, konnten NP-harte Probleme in der Polynomzeit nicht gelöst werden.

Einige NP-HART-Optimierungsprobleme können Polynomzeit sein angenähert bis zu einem konstanten Annäherungsverhältnis (insbesondere in denen in APX) oder sogar bis zu einem Annäherungsverhältnis (die in PTAs oder Fptas).

Beispiele

Ein Beispiel für ein NP-hartes Problem ist die Entscheidung Summenproblem: Fügt eine nicht leere Teilmenge von ihnen bei einer Reihe von Ganzzahlen auf Null hinzu? Das ist ein Entscheidungsproblem und ist zufällig NP-Complete. Ein weiteres Beispiel für ein NP-harte Problem ist das Optimierungsproblem beim Finden der am wenigsten günstigen zyklischen Route durch alle Knoten eines gewichteten Diagramms. Dies ist allgemein bekannt als die Problem mit reisenden Verkäufern.[7]

Es gibt Entscheidungsprobleme, die sind Np-harte aber nicht NP-Complete so wie die Problem stoppen. Das ist das Problem, bei dem "angesichts eines Programms und seiner Eingabe es für immer laufen wird?" Das ist ein Jawohl/nein Frage und so ist ein Entscheidungsproblem. Es ist leicht zu beweisen, dass das Anstill-Problem NP-HART ist, aber nicht NP-Complete. Zum Beispiel die Boolesche Zufriedenheitsproblem kann auf das Stoppproblem reduziert werden, indem es in die Beschreibung von a umgewandelt wird Turing Maschine das versucht alles Wahrheitswert Aufgaben und wenn es eine findet, die die Formel erfüllt, die sie anhält, und ansonsten in eine unendliche Schleife geht. Es ist auch leicht zu erkennen, dass das Anhaltsproblem nicht in liegt Np Da alle Probleme in NP in einer begrenzten Anzahl von Operationen leiden, ist das Problem im Allgemeinen im Allgemeinen unentscheidbar. Es gibt auch NP-harte Probleme, die auch nicht sind NP-Complete Noch Unentscheidbar. Zum Beispiel die Sprache von echte quantifizierte Boolesche Formeln ist lehnte in Polynomraum, aber nicht in nicht deterministischer Polynomzeit (es sei denn, NP = PSPACE).[8]

NP-Namenskonvention

NP-harte Probleme müssen keine Elemente der Komplexitätsklasse NP sein. Da spielt NP eine zentrale Rolle in RechenkomplexitätEs wird als Grundlage mehrerer Klassen verwendet:

Np
Klasse von rechnerischen Entscheidungsproblemen, für die eine bestimmte Jawohl-Die Lösung kann als Lösung in der Polynomzeit durch eine deterministische Turing -Maschine (OR) verifiziert werden lösbar durch eine nicht deterministisch Turing -Maschine in Polynomzeit).
Np-harte
Klasse von Problemen, die mindestens so schwierig sind wie die schwierigsten Probleme in NP. Probleme, die NP-Herd sind, müssen keine Elemente von NP sein; In der Tat sind sie möglicherweise nicht einmal lehbar.
NP-Complete
Klasse von Entscheidungsproblemen, die die schwierigsten Probleme in NP enthält. Jedes NP-Complete-Problem muss in NP sein.
NP-Easy
Höchstens so hart wie NP, aber nicht unbedingt in NP.
NP-äquivalent
Entscheidungsprobleme, die sowohl NP-Hard als auch NP-Easy sind, aber nicht unbedingt in NP.
NP-Intermediate
Wenn P und NP unterschiedlich sind, gibt es in der Region von NP Entscheidungsprobleme, die zwischen P und den NP-Complete-Problemen fallen. (Wenn P und NP dieselbe Klasse sind, bestehen NP-Intermediate-Probleme nicht, da in diesem Fall jedes NP-Complete-Problem in P fallen würde, und per Definition kann jedes Problem in NP auf ein NP-Complete-Problem reduziert werden. ))

Anwendungsbereiche

NP-HARD-Probleme werden häufig mit Regeln mit basierten Sprachen in Bereichen behandelt, darunter:

Verweise

  1. ^ a b c Leeuwen, Jan Van, ed. (1998). Handbuch der theoretischen Informatik. Vol. A, Algorithmen und Komplexität. Amsterdam: Elsevier. ISBN 0262720140. OCLC 247934368.
  2. ^ Knuth, Donald (1974). "PostScript über NP-harte Probleme". ACM Sigact News. 6 (2): 15–16. doi:10.1145/1008304.1008305. S2CID 46480926.
  3. ^ Daniel Pierre Bovet; Pierluigi Crescenzi (1994). Einführung in die Theorie der Komplexität. Prentice Hall. p. 69. ISBN 0-13-915380-2.
  4. ^ "Shtetl-optimiert» Blog-Archiv »Der wissenschaftliche Fall für p ≠ np". www.scottaaronson.com. Abgerufen 2016-09-25.
  5. ^ "Phys771 Vortrag 6: P, NP und Freunde". www.scottaaronson.com. Abgerufen 2016-09-25.
  6. ^ V. J. Rayward-Smith (1986). Ein erster Kurs in der Berechnungsfähigkeit. Blackwell. p. 159. ISBN 0-632-01307-9.
  7. ^ Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985), Das Problem des reisenden Verkäufers: Eine geführte Tour durch kombinatorische Optimierung, John Wiley & Sons, ISBN 0-471-90413-9.
  8. ^ Genauer gesagt ist diese Sprache PSPACE-Complete;Siehe zum Beispiel, Wegener, Ingo (2005), Komplexitätstheorie: Untersuchung der Grenzen effizienter Algorithmen, Springer, p.189, ISBN 9783540210450.