"Dado un algoritmo, decida si se ejecuta en el tiempo polinomial" es este problema en NP?
-
29-09-2020 - |
Pregunta
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
Solución
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