Diferencia entre revisiones de «Problema de decisión»

Contenido eliminado Contenido añadido
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 problema''' matemático puede ser redactado para que tome 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.