Seite 1 von 1

Endlich gelöst: P ungleich NP?

Verfasst: 21. Feb 2010 14:13
von Richie
Also beim Bearbeitung von Übung 7 bin ich gerade etwas stutzig geworden
in T3 sollen wir zeigen, dass
a) L nicht Element von P ist
b) L Element von NP ist

Die Musterlösung gibt dafür auch zwei Beweise an.

Nun hieße das doch aber, dass wir gezeigt haben, dass es mindestens ein Element in NP gibt, was nicht in P enthalten ist. Woraus folgt, dass wir gezeigt haben, dass P eine echte Teilmenge von NP ist (und somit P=NP niemals gelten kann). Kann das sein? Oder hab ich jetzt was übersehen?

Oder sollte da in der Aufgabenstellung eigentlich NP-complete statt NP stehen?

Re: Endlich gelöst: P ungleich NP?

Verfasst: 21. Feb 2010 17:15
von rueckert
1) Mit NP vollständig hat die Aufgabe nichts zu tun.
2) Man beweist nicht, dass \(L \not\in \mathcal{P}\) sondern, dass \(Factoring \not\in \mathcal{P} \Rightarrow L \not\in \mathcal{P}\). Wenn man die Bedingung glaubt, hat man \(\mathcal{P} \neq \mathcal{NP}\), aber das weiß man natürlich nicht.

Re: Endlich gelöst: P ungleich NP?

Verfasst: 22. Feb 2010 13:31
von Richie
Argg, ja richtig, diese implizite Implikation ( ;) ) hab ich übersehen. Danke!