FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Praktische Informatik

[AD] polynomielle Reduktionen, P = NP...

[AD] polynomielle Reduktionen, P = NP... 2011-02-14 13:12
Anonymer User
Hallo,

Sagen wir man hat ein Problem L ∈ NP und ein Problem M ∈ NPC.
Nun gibt jemand eine Polynomialzeit-Funktion an, die M auf gewünschte Weise (ja->ja, nein->nein) auf L abbildet und beweist diese etc. Es gilt also nun nach Definition L ∈ NPC.

Würde nun ein kleines Genie L ∈ P beweisen, so würde insbesondere M ∈ P gelten (allgemeiner P = NP = NPC), denn man könnte jede Eingabe für M in die Funktion oben einspeisen, dessen Ausgabe mit dem Polynomialzeit-Algorithmus von L auswerten und dies ausgeben.
So weit, so gut.


Was, wenn nun aber jemand M ∈ P zeigt? Es würde auch hier P = NP = NPC folgen, also insbesondere L ∈ P. Nur warum ist L plötzlich auch in P? Eine Konstruktion à la "wir geben die Eingabe der Funktion und leiten das weiter an den pol.-Algorithmus für M" scheitert, weil man ja gar keine Funktion hat, die L auf M reduziert.

Wie lautet hier die Argumentation?


Ich bedanke mich schon im Voraus für hilfreiche Antworten und Hinweise auf Denkfehler meinerseits=)

RE: [AD] polynomielle Reduktionen, P = NP... 2011-02-14 13:29
Wulf
Alle NP-Probleme lassen sich laut Definition auf die NP-Vollständigen Probleme reduzieren.

RE: [AD] polynomielle Reduktionen, P = NP... 2011-02-14 13:34
T4Y
Etwas ausführlicher gesagt, gilt ja folgendes:
Gegeben eine Sprache M in NPC. Falls M in P ist, gilt damit dann NP=P (folgt aus der Definition der Klasse NPC).
Da L in NP war, gilt also auch, dass es ab sofort in P ist.

RE: [AD] polynomielle Reduktionen, P = NP... 2011-02-14 13:49
Anonymer User
Ich glaub jetzt hab ichs endlich..
Sollte man für ein Problem, das in NP aber nicht NPC ist, zeigen können, dass es sogar in P liegt, wäre das ja noch kein Durchbruch. Danke für die Antwort, Wolf :)

RE: [AD] polynomielle Reduktionen, P = NP... 2011-02-14 13:53
Anonymer User
Ein Dankeschön auch an Tay :)
Was ich ganz vernachlässigt hatte war ja, dass man jedes Problem aus NP auf die Probleme von NPC reduzieren kann.

RE: [AD] polynomielle Reduktionen, P = NP... 2011-02-14 13:58
Wulf
Sollte man für ein Problem, das in NP aber nicht NPC ist, zeigen können, dass es sogar in P liegt, wäre das ja noch kein Durchbruch.
Alle Probleme aus P liegen in NP und (vermutlich) nicht in NPC. Zu zeigen, dass ein P-Problem in P liegt ist trivial.