HU-3-3

Question

"Was ändert sich, wenn man annimmt, dass P = NP gilt?

Lösung: Dann wäre (3) auch richtig, denn dann sind alle Probleme in P außer E * und ∅ NP-vollständig (und gleichzeitig in Polynomialzeit lösbar).

 

Könnte mir jemand erklären was es mit E* und ∅  im Bezug auf NP-vollständige Probleme auf sich hat?

Danke

Comments

Versuchen Sie doch mal, irgendein Problem auf E* oder die leere Menge zu reduzieren... Das kann nicht funktionieren, nicht in Polynomialzeit und auch nicht irgendwie anders. Kommen Sie selbst drauf, warum? Überlegen Sie, was diese beiden Sprachen so besonders macht im Vergleich zu jeder anderen Sprache.