[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=)
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=)