"Dato un algoritmo, decidi se funziona in tempo polinomiale" è questo problema in NP?
-
29-09-2020 - |
Domanda
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
Soluzione
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