"Dato un algoritmo, decidi se funziona in tempo polinomiale" è questo problema in NP?

Question

Questo problema non è decidabile (riducibile per fermare il problema) ma è semi-decidabile e non è verificabile (poiché quelle due definizioni sono equivalenti: Come dimostrare semi-decidabile= verificabile? ).

Tuttavia, questo problema è in Poly-Time verificabile?

Un problema decisionale $ P $ è Poly Time verificabile IFF Se c'è un algoritmo

Answer 1

no.Se il problema è stato verificato in polinomiale, sarebbe solvibile in tempo esponenziale e quindi decidabile;Ma sappiamo già che non è decidabile.

Perché in tempo esponenziale?Perché $ V $ funziona in tempo $ | w | ^ k $ , può leggere al massimo $ | w | ^ k $ bit dell'ingresso.Quindi, è sufficiente per enumerare tutte le corde possibili $ c $ di lunghezza al massimo $ | w | ^ k $ , e eseguire $ V $ su ciascuno di essi.Il tempo di esecuzione sarà di $ 2 ^ {| w | ^ k} $ , che è finita e quindi sufficiente per rendere il problema originale decidabile.