Reduktion auf NP
-
Gut, das meinte ich. Ich habe mich wohl nicht genau ausgedrückt. Wenn NP und P dieselbe Menge wären, dann müsste man nicht mehr von NP sprechen.
Danke
-
Michael E. schrieb:
(Naja, ganz korrekt ist das je nach Definition nicht. In einer Vorlesung von mir liegen beispielsweise in NP nur Entscheidungsprobleme, während in P alle möglichen Probleme liegen, für die es einen Polynomialalgorithmus gibt.)
Ich hab's so gelernt, daß du ein Problem auf verschiedene Arten formulieren kannst (hier mal am Beispiel des Cliquenproblems):
* Entscheidungsproblem (hat der Graph x eine Clique der Größe k?)
* Konstruktionsproblem (aus welchen Knoten besteht die größte Clique des Graphen k?)
* Optimierungsproblem (wie groß ist die größte Clique des Graphen k?)Aus Sicht der Komplexität sind diese drei Probleme gleichwertig und bei einer deterministischen TM kannst du auch ein klares Ausgabeverhalten definieren. Bei einer nichtdeterministischen TM gibt es zwar eine klar definierte Akzeptanz (wenn irgendeine Berechnung akzeptiert, heißt die Ausgabe JA), aber für detailliertere Ausgaben wäre die Festlegung wohl schwieriger.
-
CStoll schrieb:
Ich hab's so gelernt, daß du ein Problem auf verschiedene Arten formulieren kannst (hier mal am Beispiel des Cliquenproblems):
* Entscheidungsproblem (hat der Graph x eine Clique der Größe k?)
* Konstruktionsproblem (aus welchen Knoten besteht die größte Clique des Graphen k?)
* Optimierungsproblem (wie groß ist die größte Clique des Graphen k?)Aus Sicht der Komplexität sind diese drei Probleme gleichwertig
Das ist oftmals der Fall, aber nicht allgemeingültig: Wenn die Entscheidungsvariante in NP liegt, muss die Konstruktionsvariante (die in meiner aktuellen Vorlesung lustigerweise Optimierungsvariante heißt
) nicht auch in NP liegen. Ein Beispiel dafür weiß ich leider nicht.Edit: Bei der Konstruktionsvariante meinst du sicherlich: Gib eine größte Clique für einen gegebenen Graphen an.
-
Michael E. schrieb:
Das ist oftmals der Fall, aber nicht allgemeingültig: Wenn die Entscheidungsvariante in NP liegt, muss die Konstruktionsvariante (die in meiner aktuellen Vorlesung lustigerweise Optimierungsvariante heißt
) nicht auch in NP liegen. Ein Beispiel dafür weiß ich leider nicht.Ja, die Namen hatte ich nicht mehr im Kopf, liegt auch schon fas zehn Jahre her, daß ich das gelernt habe. Der Punkt war, soweit ich mich erinnern kann: Wenn du einen Algorithmus hast, der eine der Varianten löst, kannst du mit polynomiellem Mehraufwand die beiden anderen auch lösen.
(und das läuft mitunter darauf hinaus, daß du alle potentielle Lösungen (nichtdeterministisch) ermitteln kannst und anschließend prüfst, ob sie korrekt sind)
-
CStoll schrieb:
Der Punkt war, soweit ich mich erinnern kann: Wenn du einen Algorithmus hast, der eine der Varianten löst, kannst du mit polynomiellem Mehraufwand die beiden anderen auch lösen.
(und das läuft mitunter darauf hinaus, daß du alle potentielle Lösungen (nichtdeterministisch) ermitteln kannst und anschließend prüfst, ob sie korrekt sind)Gerade das denke ich nicht. Wenn ich dran denke, kann ich am Montag meinen Prof fragen. Im Moment hab ich nur nen Google-Treffer für dich:
Darüber hinaus sind die Optimierungsvarianten der meisten NP-vollständigen Entscheidungsprobleme NP-äquivalent
-
Michael E. schrieb:
Gerade das denke ich nicht.
Doch! Das unser Lehrer auch gesagt. Wenn eins in polynomieller Zeit gelöst sind, dann sind alle in dieser Zeit lösbar. Deswegen würde ja NP auch ganz in P liegen. Das war ja meine Ausgangsfrage
-
freakC++ schrieb:
Michael E. schrieb:
Gerade das denke ich nicht.
Doch! Das unser Lehrer auch gesagt. Wenn eins in polynomieller Zeit gelöst sind, dann sind alle in dieser Zeit lösbar. Deswegen würde ja NP auch ganz in P liegen. Das war ja meine Ausgangsfrage
Darum gings in dem Zitat nicht.
-
@Michael: In dem Kontext dort ist leider nicht klar, ob die Ausnahmen aus dem "die meisten" jetzt leichter oder schwerer als NP sein sollen
Ich versuch mal zusammenzukratzen, was ich noch in Erinnerung habe:
Wenn ich das Entscheidungsproblem mit einer polynomiellen NTM lösen kann, kann ich das zu einer Maschine für das Optimierungsproblem ausbauen (ich probiere von 0 bis |G| alle Werte aus und frage die Maschine, ob eine Clique der Größe existiert).
Wenn ich das Optimierungsproblem lösen kann, kann ich daraus eine Maschine für das Konstruktionsproblem bauen (indem verschieden Variationen des Graphen an die gegebene Maschine geschickt werden).
Wenn ich das Konstruktionsproblem lösen kann, ist die Lösung des Entscheidungsproblems trivial.
-
CStoll schrieb:
@Michael: In dem Kontext dort ist leider nicht klar, ob die Ausnahmen aus dem "die meisten" jetzt leichter oder schwerer als NP sein sollen
Schwerer. Denn die Entscheidungsvariante kann nicht schwerer als die Optimierungsvariante sein.
Ich versuch mal zusammenzukratzen, was ich noch in Erinnerung habe:
Wenn ich das Entscheidungsproblem mit einer polynomiellen NTM lösen kann, kann ich das zu einer Maschine für das Optimierungsproblem ausbauen (ich probiere von 0 bis |G| alle Werte aus und frage die Maschine, ob eine Clique der Größe existiert).Damit bist du aber nicht mehr polynomiell, da die Eingabezahlen logarithmisch kodiert werden können. Schau dir z. B. Knapsack an: Du willst den maximalen Nutzwert p bestimmen. Dafür würdest du bei Eingabelänge n alle Zahlen von 0 bis 2^n ausprobieren. In diesem konkreten Fall kann man sich übrigens mit einer binären Suche helfen. Damit bleibt man polynomiell.
Wenn ich das Optimierungsproblem lösen kann, kann ich daraus eine Maschine für das Konstruktionsproblem bauen (indem verschieden Variationen des Graphen an die gegebene Maschine geschickt werden).
In diesem konkreten Fall ja. Aber im Allgemeinen hast du überhaupt keinen Graphen, den du rumschicken kannst
-
Michael E. schrieb:
Wenn ich das Optimierungsproblem lösen kann, kann ich daraus eine Maschine für das Konstruktionsproblem bauen (indem verschieden Variationen des Graphen an die gegebene Maschine geschickt werden).
In diesem konkreten Fall ja. Aber im Allgemeinen hast du überhaupt keinen Graphen, den du rumschicken kannst
Du hast immer irgendeine Art von Struktur, die du für das Konstruktionsproblem aufbauen mußt - bei Knapsack kannst du z.B. alle Gegenstände nehmen und abfragen, ob das Optimum gleich bleibt, wenn du den Gegenstand weglässt.
(wie gesagt, meine Studienzeit liegt schon etwas zurück - und ich bin mir auch nicht sicher, ob ich meine Mitschriften und Scripte von damals noch finde)
-
CStoll schrieb:
Michael E. schrieb:
Wenn ich das Optimierungsproblem lösen kann, kann ich daraus eine Maschine für das Konstruktionsproblem bauen (indem verschieden Variationen des Graphen an die gegebene Maschine geschickt werden).
In diesem konkreten Fall ja. Aber im Allgemeinen hast du überhaupt keinen Graphen, den du rumschicken kannst
Du hast immer irgendeine Art von Struktur, die du für das Konstruktionsproblem aufbauen mußt - bei Knapsack kannst du z.B. alle Gegenstände nehmen und abfragen, ob das Optimum gleich bleibt, wenn du den Gegenstand weglässt.
(wie gesagt, meine Studienzeit liegt schon etwas zurück - und ich bin mir auch nicht sicher, ob ich meine Mitschriften und Scripte von damals noch finde)Du kannst über das Konstruieren dieser Struktur aber eben im Allgemeinen nichts sagen. Schau dir z. B. Partition an, wenn du dort ein Element weglässt, erhälst du sofort ein anderes Ergebnis. Woher weiß ich nun, dass das Konstruieren einer optimalen Lösung schnell funktioniert?
-
CStoll: Ich bin dir in diesem Thread noch ne Antwort schuldig, deshalb kram ich ihn nochmal hervor.
Ein praktisch relevantes Problem ist die Primfaktorzerlegung. Bei diesem weiß man, dass die Entscheidungsvariante in P liegt. Die Optimierungsvariante, d. h. das Bestimmen der Primfaktoren, ist aber wahrscheinlich nicht in P.