Entscheiden Sie bei einem Algorithmus, ob es in der Polynomzeit läuft "ist dieses Problem in NP?
-
29-09-2020 - |
Frage
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
Lösung
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