Endlich gelöst: P ungleich NP?

Moderator: Post Quantum Cryptography

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Endlich gelöst: P ungleich NP?

Beitrag von Richie » 21. Feb 2010 14:13

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?
There are only 10 types of people in the world:
Those who understand binary and those who don't

rueckert
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 9. Apr 2008 09:25

Re: Endlich gelöst: P ungleich NP?

Beitrag von rueckert » 21. Feb 2010 17:15

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.

Richie
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 25. Okt 2005 13:03
Wohnort: Darmstadt
Kontaktdaten:

Re: Endlich gelöst: P ungleich NP?

Beitrag von Richie » 22. Feb 2010 13:31

Argg, ja richtig, diese implizite Implikation ( ;) ) hab ich übersehen. Danke!
There are only 10 types of people in the world:
Those who understand binary and those who don't

Antworten

Zurück zu „Post-Quantum Cryptography“