Entscheiden Sie bei einem Algorithmus, ob es in der Polynomzeit läuft "ist dieses Problem in NP?

Question

Dieses Problem ist nicht entschieden (reduzierbar zum Anhalten des Problems), ist jedoch semi-entschlossen und dadurch überprüfbar (da diese beiden Definitionen gleichwertig sind: Wie erweist man semi-entschieden= überprüfbar? ).

ist dieses Problem jedoch, die Poly-Zeit überprüfbar ist?

ein Entscheidungsproblem $ P $ ist Poly-Zeit-überprüfbar IFF Es gibt einen Algorithmus

Answer 1

nein.Wenn das Problem auf Polynomzeit überprüfbar war, wäre er in exponentiellen Zeit lösbar und somit entschieden;Aber wir wissen schon, dass das nicht entmutigt ist.

Warum in exponentiellen Zeiten?Denn $ V $ läuft in der Zeit $ | w | ^ k $ , kann es höchstens $ | W | ^ K $ Bits der Eingabe.So genügt es, alle möglichen Saiten aufzulisten $ C $ der Länge höchstens $ | W | ^ k $ , und führen Sie $ V $ auf jedem von ihnen.Die Laufzeit ist ungefähr $ 2 ^ {| w | ^ k} $ , das endlich und damit ausreichend ist, um das ursprüngliche Problem entschieden zu machen.