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!
 

 

Wieso liegt das Problem in NP?

–1 Punkt
32 Aufrufe
B ist np schwer und nichtdeterministisch in Polynomialzeit lösbar, warum können wir daraus folgern, dass jenes Problem in NP liegt? Es ist schließlich nirgends die Rede von einer Turing Maschine, die das Problem in polynomieller Zeit löst?!
Gefragt 22, Okt 2014 in BER-AI von utdbu utdbu Tutor(in) (106,580 Punkte)  

2 Antworten

0 Punkte
"B ist (...) nichtdeterministisch in Polynomialzeit lösbar"

das heißt genau, dass eine nichtdeterministische TM existiert, die das Problem in polynomieller Zeit löst => B liegt laut Definition eines Problems aus NP in NP

Wenn wir von [nicht]deterministich in XY-Zeit lösbar reden, ist implizit immer auf einer entsprechenden TM gemeint.

Gruß,

Tobias (Tutor)
Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
0 Punkte

Wie Sie durch die erweiterte Churche These wissen, muss man nicht von Turingmaschinen reden, da wir davon ausgehen, dass alle Berechnungsmodelle bis auf polynomielle Faktoren gleiche Zeitkomplexität haben.

Viele Grüße

Lukas König

 

Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...