En la teoría de la computabilidad y la teoría de la complejidad computacional , un problema de decisión es un problema computacional que puede plantearse como una pregunta de sí o no sobre los valores de entrada. Un ejemplo de un problema de decisión es decidir mediante un algoritmo si un número natural dado es primo . Otro es el problema "dados dos números x e y , ¿ x divide a y exactamente ?". La respuesta es "sí" o "no" dependiendo de los valores de x e y . Un método para resolver un problema de decisión, dado en forma de algoritmo , se denomina procedimiento de decisión para ese problema. Un procedimiento de decisión para el problema de decisión "dados dos números x e y , ¿ x divide a y exactamente ?" daría los pasos para determinar si x divide a y exactamente . Uno de estos algoritmos es la división larga . Si el resto es cero, la respuesta es "sí", de lo contrario es "no". Un problema de decisión que puede resolverse mediante un algoritmo se denomina decidible .
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 en matemáticas son indecidibles .
El campo de la complejidad computacional clasifica los problemas de decisión decidibles según su dificultad para resolverlos. "Difícil", en este sentido, se describe en términos de los recursos computacionales que necesita el algoritmo más eficiente para un determinado problema. El campo de la teoría de la recursión , por su parte, clasifica los problemas de decisión indecidibles según el grado de Turing , que es una medida de la no computabilidad inherente a cualquier solución.
Un problema de decisión es una pregunta de sí o no sobre un conjunto infinito de entradas. Tradicionalmente, se define el problema de decisión como el conjunto de entradas posibles junto con el conjunto de entradas para las que la respuesta es sí . [1]
Estas entradas pueden ser números naturales, pero también pueden ser valores de algún otro tipo, como cadenas binarias o cadenas sobre algún otro alfabeto . El subconjunto de cadenas para el que el problema devuelve "sí" es un lenguaje formal y, a menudo, los problemas de decisión se definen como lenguajes formales.
Utilizando una codificación como la numeración de Gödel , cualquier cadena puede ser codificada como un número natural, mediante lo cual un problema de decisión puede ser definido como un subconjunto de los números naturales. Por lo tanto, el algoritmo de un problema de decisión es calcular la función característica de un subconjunto de los números naturales.
Un ejemplo clásico de un problema de decisión decidible es el conjunto de números primos. Es posible decidir efectivamente si un número natural dado es primo probando cada factor no trivial posible. Aunque se conocen métodos mucho más eficientes de prueba de primalidad , la existencia de cualquier método efectivo es suficiente para establecer la decidibilidad.
Un problema de decisión es decidible o efectivamente solucionable si el conjunto de entradas (o números naturales) para los que la respuesta es sí es un conjunto recursivo . Un problema es parcialmente decidible , semidecidible , solucionable o demostrable si el conjunto de entradas (o números naturales) para los que la respuesta es sí es un conjunto recursivamente enumerable . Los problemas que no son decidibles son indecidibles . Para ellos no es posible crear un algoritmo, eficiente o no, que los resuelva.
El problema de la detención es un importante problema de decisión indecidible; para más ejemplos, consulte la lista de problemas indecidibles .
Los problemas de decisión se pueden ordenar según la reducibilidad de muchos a uno y relacionarlos con reducciones factibles, como las reducciones en tiempo polinomial . Se dice que un problema de decisión P está completo para un conjunto de problemas de decisión S si P es un miembro de S y cada problema en S se puede reducir a P. Los problemas de decisión completos se utilizan en la teoría de la complejidad computacional para caracterizar las clases de complejidad de los problemas de decisión. Por ejemplo, el problema de satisfacibilidad booleano está completo para la clase NP de problemas de decisión bajo la reducibilidad en tiempo polinomial.
Los problemas de decisión están estrechamente relacionados con los problemas de función , que pueden tener respuestas más complejas que un simple "sí" o "no". Un problema de función correspondiente es "dados dos números x e y , ¿cuál es el resultado de x dividido por y ?".
Un problema de función consiste en una función parcial f ; el "problema" informal es calcular los valores de f en las entradas para las que está definida.
Todo problema de función puede convertirse en un problema de decisión; el problema de decisión es simplemente el gráfico de la función asociada. (El gráfico de una función f es el conjunto de pares ( x , y ) tales que f ( x ) = y .) Si este problema de decisión fuera efectivamente solucionable, entonces el problema de función también lo sería. Sin embargo, esta reducción no respeta la complejidad computacional. Por ejemplo, es posible que el gráfico de una función sea decidible en tiempo polinomial (en cuyo caso el tiempo de ejecución se calcula como una función del par ( x , y )) cuando la función no es computable en tiempo polinomial (en cuyo caso el tiempo de ejecución se calcula como una función de x solamente). La función f ( x ) = 2 x tiene esta propiedad.
Todo problema de decisión puede convertirse en un problema funcional que consiste en calcular la función característica del conjunto asociado al problema de decisión. Si esta función es computable, entonces el problema de decisión asociado es decidible. Sin embargo, esta reducción es más liberal que la reducción estándar que se utiliza en la complejidad computacional (a veces llamada reducción de muchos-uno en tiempo polinomial); por ejemplo, la complejidad de las funciones características de un problema NP-completo y su complemento co-NP-completo es exactamente la misma, aunque los problemas de decisión subyacentes no se consideren equivalentes en algunos modelos típicos de computación.
A diferencia de los problemas de decisión, para los cuales solo hay una respuesta correcta para cada entrada, los problemas de optimización se ocupan de encontrar la mejor respuesta a una entrada particular. Los problemas de optimización surgen de manera natural en muchas aplicaciones, como el problema del viajante de comercio y muchas preguntas en programación lineal .
Los problemas de función y optimización se transforman a menudo en problemas de decisión al considerar la cuestión de si la salida es igual o menor que un valor dado. Esto permite estudiar la complejidad del problema de decisión correspondiente; y en muchos casos, la función original o el problema de optimización se pueden resolver resolviendo su problema de decisión correspondiente. Por ejemplo, en el problema del viajante de comercio, el problema de optimización es producir un recorrido con un peso mínimo. El problema de decisión asociado es: para cada N , decidir si el grafo tiene algún recorrido con un peso menor que N . Al responder repetidamente el problema de decisión, es posible encontrar el peso mínimo de un recorrido.
Dado que la teoría de los problemas de decisión está muy bien desarrollada, la investigación en teoría de la complejidad se ha centrado tradicionalmente en los problemas de decisión. Los problemas de optimización en sí mismos siguen siendo de interés en la teoría de la computabilidad, así como en campos como la investigación de operaciones .