“Dado um algoritmo, decida se ele roda em tempo polinomial” esse problema está em NP?

Question

Este problema não é decidível (redutível ao problema da parada), mas é semidecidível e, portanto, verificável (já que essas duas definições são equivalentes: Como provar semidecidível = verificável?).

No entanto, esse problema é verificável em vários tempos?

Um problema de decisão $P$ é poli-tempo verificável se existir um algoritmo 𝑉 chamado verificador tal que se $P(w)=$𝑌𝐸𝑆 então há uma string $c$ st. $𝑉(w,c)=$𝑌𝐸𝑆, se $P(w)=𝑁𝑂$ então para todas as strings $c$, $𝑉(w,c)=$𝑁𝑂 e V correm $O(w^{k})$ para alguma constante $k$ para todas as entradas $w$.

Answer 1

Não.Se o problema fosse verificável em tempo polinomial, seria solucionável em tempo exponencial e, portanto, decidível;mas já sabemos que isso não é decidível.

Por que em tempo exponencial?Porque $V$ corre no tempo $|w|^k$, ele pode ler no máximo $|w|^k$ bits da entrada.Então, basta enumerar todas as strings possíveis $c$ de comprimento no máximo $|w|^k$, e corra $V$ em cada um deles.O tempo de execução será de cerca $2^{|w|^k}$, que é finito e, portanto, suficiente para tornar o problema original decidível.