Warum ist H nicht in NP (A41b)?

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Warum ist H nicht in NP (A41b)?
Um zu zeigen, dass H nicht NP-vollständig ist, wird in A41b argumentiert, dass H nicht in NP ist, weil H nicht entscheidbar ist. Aber laut Definition von NP würde es doch ausreichen, wenn H in Polynomzeit von einer NTM akzepziert werden würde, sie müsste doch nicht entscheidbar sein!?


Das passt so schon.
Fuer jede NTM gilt, wenns fuer eine Eingabe eine Loesung gibt, dann wird diese auch gefunden.
Fuer jede Sprache in NP gilt, es muss eine O(f(n))-zeitbeschraenkte NTM geben, die diese Sprache akzeptiert.
Jetzt vernachlaessige mal die Landau-Notation und denk dir du haettest die tatsaechliche Laufzeit g(n), d.h. mit allen Faktoren und Termen, die sonstwegfallen wuerden, gegeben (die Vorraussetzung darfst du machen).
Nun kannst du wiederum die ersten g(n)-Schritte in allen moeglichen Abfolgen simulieren und, wenn die Simulaton zu Ende ist, ohne eine Loesung gefunden zu haben, dann ist die Eingabe nicht in der Sprache. Somit ist die Sprache wiederum entscheidbar.


Achso ok, also so wie ich das verstehe ist NP entscheidbar, da man immer einfach alle Möglichkeiten durchprobieren kann (brute force), aber eben nicht zwingend in Polynomzeit. Die Akzeptanz erfolgt garantiert in Polynomzeit. Und wenn nicht, dann kann man sich in endlicher Zeit sicher sein, dass das entsprechende Wort nicht zu der jeweiligen NP-Sprache gehört, und somit die NP-Sprache entscheiden. Kann man das so sagen?


Die garantierte Akzeptanz, falls das Wort in der Sprache enthalten ist, erlaubt einen brute force Ansatz, ja.