Diferencia entre revisiones de «Problema de decisión»

Contenido eliminado Contenido añadido
Julie (discusión · contribs.)
mSin resumen de edición
Línea 12:
* Las frases que describen una [[máquina de Turing]] y una cinta de entrada para esta máquina tal que [[problema de parada|la máquina se para]] en un tiempo finito al procesar esa entrada.
 
Los problemas de decisión son interesantes dado que todos los problemaproblemas matemáticomatemáticos puedepueden ser redactadoredactadso para que tometomen la forma de un problema de decisión. Las soluciones al problema de decisión y al problema original se diferencian a lo sumo por un factor lineal.