Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

HU-3-3

–1 Punkt
38 Aufrufe
"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
Gefragt 21, Jul 2016 in AU-3-1 von usdqz usdqz Lernwillige(r) (440 Punkte)  
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.

Ihre Antwort

Ihr anzuzeigender Name (optional):
Datenschutzhinweis: Ihre E-Mail-Adresse wird ausschließlich benutzt, um Ihnen Benachrichtigungen zu schicken. Es gilt die Datenschutzerklärung.
Anti-Spam-Abfrage (Captcha):
Bitte loggen Sie ein oder registrieren sich, um diese Abfrage (Captcha) zu vermeiden.
...