"NP-complete" Optimierungsprobleme

24

Ich bin etwas verwirrt über einige Begriffe, die ich in Bezug auf die Komplexität von Optimierungsproblemen gefunden habe. In einer Algorithmusklasse hatte ich das große Sparsamkeitsproblem , das als NP-vollständig beschrieben wurde. Ich bin mir jedoch nicht ganz sicher, was der Begriff NP-vollständig im Zusammenhang mit einem Optimierungsproblem bedeutet. Bedeutet dies nur, dass das entsprechende Entscheidungsproblem NP-vollständig ist? Und bedeutet dies, dass das Optimierungsproblem möglicherweise schwieriger ist (möglicherweise außerhalb von NP)?

Insbesondere mache ich mir Sorgen darüber, dass ein NP-vollständiges Entscheidungsproblem zwar polynomiell zeitlich überprüfbar ist, eine Lösung für ein entsprechendes Optimierungsproblem jedoch nicht polynomiell zeitlich überprüfbar zu sein scheint. Bedeutet das, dass das Problem nicht wirklich in NP liegt, oder ist die Verifizierbarkeit der Polynomzeit nur ein Merkmal von NP-Entscheidungsproblemen?

Aniket Schneider
quelle
3
Diese Frage
Ran G.
1
@RanG., Ich bin nicht sicher, ob dies ein genaues Duplikat ist.
Kaveh
@Kaveh du hast recht, aber die großartige Antwort von uli beantwortet diese Frage vollständig.
Ran G.
@RanG., Es kann mehr als eine gute Antwort geben. :)
Kaveh

Antworten:

13

Ein Versuch einer Teilantwort:

Entscheidungsprobleme wurden bereits einige Zeit untersucht, bevor Optimierungsprobleme in dem Sinne auftauchten, wie sie aus der Perspektive der Approximationsalgorithmen behandelt werden.

Sie müssen vorsichtig sein, wenn Sie Konzepte aus Entscheidungsproblemen übernehmen. Dies kann durchgeführt werden und es kann eine genaue Vorstellung der NP-Vollständigkeit für Optimierungsprobleme gegeben werden. Schau dir diese Antwort an . Es unterscheidet sich natürlich von der NP-Vollständigkeit bei Entscheidungsproblemen, basiert aber auf den gleichen Ideen (Reduktionen).

Wenn Sie mit einem Optimierungsproblem konfrontiert sind, das keine Überprüfung mit einer praktikablen Lösung zulässt, können Sie nicht viel tun. Deshalb geht man normalerweise davon aus, dass:

  • Wir können effizient überprüfen, ob die Eingabe tatsächlich eine gültige Instanz unseres Optimierungsproblems ist.
  • Die Größe der möglichen Lösungen ist polynomial durch die Größe der Eingaben begrenzt.
  • Wir können effizient überprüfen, ob eine Lösung eine realisierbare Lösung der Eingabe ist.
  • Der Wert einer Lösung kann effizient bestimmt werden.

Ansonsten können wir nicht viel hoffen.

NPNPNP

Wenn Sie überprüfen möchten, ob eine Lösung nicht nur machbar, sondern auch optimal ist, würde ich sagen, dass dies genauso schwierig ist wie die Lösung des ursprünglichen Optimierungsproblems, da Sie, um eine gegebene machbare und möglicherweise optimale Lösung als nicht optimal zu widerlegen, dies tun Sie müssen eine bessere Lösung finden, die es möglicherweise erforderlich macht, die wirklich optimale Lösung zu finden.

Dies bedeutet jedoch nicht, dass das Optimierungsproblem schwieriger ist. Siehe diese Antwort , die natürlich von den genauen Definitionen abhängt.

uli
quelle
Können Sie bitte einen Artikel oder eine Referenz angeben, in der ich weitere Informationen zu einer genauen Definition, Reduzierung usw. der NP-Härte für Optimierungsprobleme finden kann? Bisher konnte ich keinen herausfinden. Das wäre sehr interessant für mich. Vielen Dank.
John Threepwood
-1

Der Grund, warum die meisten Optimierungsprobleme als P, NP, NP-vollständig usw. klassifiziert werden können, sind die Kuhn-Tucker-Bedingungen. Ich werde in Bezug auf lineare Programmierprobleme sprechen, aber die KTC gelten in vielen anderen Optimierungsproblemen. Für jedes Optimierungsproblem gibt es ein Dual. Wenn das Ziel des ursprünglichen Problems darin besteht, eine Funktion zu maximieren, muss das Dual (normalerweise) eine Funktion minimiert werden. * Durchführbare, aber nicht optimale Lösungen für das ursprüngliche Problem sind für das Dualproblem und umgekehrt nicht durchführbar / ungültig -versa. Wenn und nur wenn eine Lösung für das primäre und das duale System möglich ist, ist dies eine optimale Lösung für beide. (Technisch gesehen kann dies eine von vielen optimalen Lösungen sein, die das gleiche Ergebnis liefern.)

Das Finden einer optimalen Lösung eines Optimierungsproblems ist also gleichbedeutend mit dem Finden einer gültigen Lösung für das primäre und das duale System. Sie können Optimierungsalgorithmen verwenden, um diese Lösung zu finden, aber der Gesamtprozess ist ein Existenznachweis.

  • Wenn Sie von Minimierung zu Maximierung wechseln möchten, multiplizieren Sie die Zielfunktion mit -1.
Robert I. Eachus
quelle
3
Ich verstehe nicht, in welchem ​​Verhältnis die KKT-Bedingungen zur NP-Härte stehen. Können Sie das näher erläutern?
Diskrete Eidechse
2
Ich verstehe nicht wirklich, wie dies die Frage beantwortet. P , NP usw. sind Klassen von Entscheidungsproblemen. Optimierungsprobleme sind keine Entscheidungsprobleme, daher gehören sie definitionsgemäß nicht zu diesen Klassen .
David Richerby
2
Ich verstehe auch nicht, wie dies die Frage beantwortet - dies ist ein interessanter Kommentar, aber es scheint eine andere Frage zu beantworten als die, die gestellt wurde. In der Frage wird gefragt, was es bedeutet, zu sagen, dass ein Optimierungsproblem NP-vollständig ist und ob Optimierungsprobleme in NP vorliegen, da sie kein Entscheidungsproblem sind. Dies beschreibt, wie wir angesichts eines Optimierungsproblems (bei dem Lösungen nicht überprüfbar sind) oft ein entsprechendes Problem konstruieren können , bei dem Lösungen überprüft werden können. Sehr interessantes Zeug, aber ich bin nicht sicher, ob es die gestellte Frage beantwortet.
DW
1
@DW Der Hauptgrund, warum ich denke, dass dies die Frage nicht wirklich beantwortet, ist, dass KKT die Einstellung zusätzlich zu dem, was bereits erwähnt wurde, auf die mathematische Optimierung von "regulären" (z. B. kontinuierlichen, differenzierbaren, konvexen) Funktionen beschränkt. Diese Einstellung gilt nicht für die meisten NP-harten Probleme.
Diskrete Eidechse