Problema de decisión
En la teoría de la computabilidad y la teoría de la complejidad computacional, un problema de decisión es una pregunta en algún sistema formal con una respuesta de sí o no. La respuesta depende de los valores de los parámetros de entrada. Los problemas de decisión suelen aparecer en cuestiones matemáticas de decidibilidad, es decir, la cuestión de la existencia de un método eficaz para determinar la existencia de algún objeto o su pertenencia a un conjunto. Algunos de los problemas más importantes de las matemáticas son indecidibles.
Un problema de decisión sólo tiene dos salidas posibles, sí o no (o alternativamente 1 o 0) en cualquier entrada.
Preguntas y respuestas
P: ¿Qué es un problema de decisión?
R: Un problema de decisión es una pregunta en algún sistema formal con una respuesta de sí o no, que depende de los valores de los parámetros de entrada.
P: ¿En qué campos de estudio aparecen los problemas de decisión?
R: Los problemas de decisión suelen aparecer en cuestiones matemáticas de decidibilidad.
P: ¿Qué significa decidibilidad?
R: La decidibilidad se refiere a la cuestión de la existencia de un método eficaz para determinar la existencia de algún objeto o su pertenencia a un conjunto.
P: ¿Son decidibles todos los problemas matemáticos?
R: No, algunos de los problemas más importantes de las matemáticas son indecidibles.
P: ¿Qué es un problema indecidible?
R: Un problema indecidible es un problema para el que no existe ningún algoritmo que pueda dar siempre una respuesta afirmativa o negativa en un tiempo finito.
P: ¿La respuesta a un problema de decisión es siempre sí o no?
R: Sí, la respuesta a un problema de decisión es siempre sí o no.
P: ¿De qué depende la respuesta a un problema de decisión?
R: La respuesta a un problema de decisión depende de los valores de los parámetros de entrada.
