"Dado un algoritmo, decida si se ejecuta en el tiempo polinomial" es este problema en NP?

Question

Este problema no es decidible (reducible para detener el problema), sino que es semi-decidible y es verificable (ya que esas dos definiciones son equivalentes: ¿Cómo demostrar semi-decidible= verificable? ).

Sin embargo, ¿este problema es verificable poli-tiempo?

Un problema de decisión $ p $ es polivinílico verificable IFF hay un algoritmo

Answer 1

no.Si el problema era verificable de Polinomial, sería solucible en tiempo exponencial y, por lo tanto, decidible;Pero ya sabemos que no es decidible.

¿Por qué en tiempo exponencial?Porque $ v $ se ejecuta en el tiempo $ | w | ^ k $ , puede leer como máximo $ | w | ^ k $ bits de la entrada.Por lo tanto, basta con enumerar todas las cadenas posibles $ C $ de longitud en la mayoría $ | w | ^ k $ , y ejecute $ v $ en cada uno de ellos.El tiempo de ejecución será sobre $ 2 ^ {| w | ^ k} $ , que es finito y, por lo tanto, lo suficiente como para que el problema original sea decidible.