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!
 

 

Warum 1. Aussage nicht falsch?

0 Punkte
40 Aufrufe
Hallo,

auf Folie 5-42 steht: "Vermutung: Es gibt keinen Algorithmus, der NP-vollständige Probleme in polynomieller Zeit löst, P ungleich NP." Dann müsste doch die 1. Aussage falsch sein. Mir ist die Argumentation von den obigen Posts eigentlich auch klar, aber wenn ich diese Vermutung mit berücksichtige habe ich doch einen Widerspruch?
Gefragt 15, Nov 2014 in BER-AB von uyctv uyctv Info-Genie (19,250 Punkte)  

Eine Antwort

0 Punkte

Hallo,

das Schlagwort dort ist: "Das Problem kann verifiziert werden". NP-Probleme sind definiert als "...von nichtdet. Turingmaschinen in polynomieller Zeit berechenbare Funktionen". Übersetzt heißt das, dass eine ndet. Turingmaschine eine Lösung raten und diese anschliessend in polynomieller Zeit verifizieren kann (Folie 5-37). So ist das gemeint.

Gruß,

Adam (Tutor)

 

Beantwortet 15, Nov 2014 von uyctv uyctv Info-Genie (19,250 Punkte)  
...