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 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 xey , ¿ x divide uniformemente a y ?". 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 uniformemente a y ?" daría los pasos para determinar si x divide uniformemente a y . Uno de esos algoritmos es la división larga . Si el resto es cero la respuesta es "sí", en caso contrario es "no". Un problema de decisión que puede resolverse mediante un algoritmo se llama decidible .
Los problemas de decisión aparecen típicamente 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 .
El campo de la complejidad computacional clasifica los problemas de decisión decidibles según su dificultad de resolver. "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. Mientras tanto, el campo de la teoría de la recursividad 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. Es tradicional definir 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 las cuales el problema devuelve "sí" es un lenguaje formal y, a menudo, los problemas de decisión se definen como lenguajes formales.
Usando una codificación como la numeración de Gödel , cualquier cadena puede codificarse como un número natural, mediante lo cual se puede definir un problema de decisión como un subconjunto de los números naturales. Por tanto, el algoritmo de un problema de decisión consiste en calcular la función característica de un subconjunto de números naturales.
Un ejemplo clásico de 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 todos los factores no triviales posibles. Aunque se conocen métodos mucho más eficientes de prueba de primalidad , la existencia de cualquier método eficaz 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 el cual 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 el cual la respuesta es sí es un conjunto recursivamente enumerable . Los problemas que no son decidibles son indecidibles . Para aquellos 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 obtener más ejemplos, consulte la lista de problemas indecidibles .
Los problemas de decisión se pueden ordenar según la reducibilidad de muchos uno y relacionarse con reducciones factibles, como las reducciones de tiempo polinomial . Se dice que un problema de decisión P es completo para un conjunto de problemas de decisión S si P es miembro de S y cada problema en S puede reducirse a P. Los problemas de decisión completos se utilizan en teoría de la complejidad computacional para caracterizar clases de complejidad de problemas de decisión. Por ejemplo, el problema de satisfacibilidad booleano está completo para la clase NP de problemas de decisión bajo 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 xey , ¿ cuánto es x dividido por y ?".
Un problema de función consta de una función parcial f ; el "problema" informal es calcular los valores de f en las entradas para las que está definido.
Todo problema de función puede convertirse en un problema de decisión; el problema de decisión es simplemente la gráfica de la función asociada. (La gráfica 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 la función también lo sería. Sin embargo, esta reducción no respeta la complejidad computacional. Por ejemplo, es posible que la gráfica 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 polinómico (en el cual el tiempo de ejecución del caso se calcula como una función de x únicamente). La función f ( x ) = 2 x tiene esta propiedad.
Todo problema de decisión se puede convertir en un problema de función de 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 utilizada en complejidad computacional (a veces llamada reducción 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 pueden no considerarse equivalentes en algunos modelos típicos de computación.
A diferencia de los problemas de decisión, para los cuales sólo hay una respuesta correcta para cada entrada, los problemas de optimización se ocupan de encontrar la mejor respuesta para una entrada en particular. Los problemas de optimización surgen naturalmente en muchas aplicaciones, como el problema del viajante y muchas preguntas sobre programación lineal .
Los problemas de función y optimización a menudo se transforman en problemas de decisión al considerar la cuestión de si la salida es igual o menor o igual a un valor dado. Esto permite estudiar la complejidad del correspondiente problema de decisión; y en muchos casos la función original o el problema de optimización se puede resolver resolviendo su correspondiente problema de decisión. Por ejemplo, en el problema del viajante, 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 gráfico tiene algún recorrido con peso menor que N. Respondiendo repetidamente al problema de decisión, es posible encontrar el peso mínimo de un recorrido.
Debido a que la teoría de los problemas de decisión está muy bien desarrollada, la investigación en teoría de la complejidad generalmente se ha centrado 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 .