Wieso liegt das Problem in NP?

Question

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?!

Answer 1

"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)

Answer 2

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