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 un problema computacional que puede plantearse como una pregunta de sí o no sobre un conjunto de valores de entrada. Un ejemplo de problema de decisión es determinar si un número natural dado es primo . Otro ejemplo es el problema: "dados dos números x e y , ¿es x divisible exactamente por y ?".

Un procedimiento de decisión para un problema de decisión es un método algorítmico que responde a la pregunta de sí o no para todas las entradas, y un problema de decisión se denomina decidible si existe un procedimiento de decisión para él. Por ejemplo, el problema de decisión "dados dos números x e y , ¿es x divisible por y ?" es decidible, ya que existe un procedimiento de decisión llamado división larga que proporciona los pasos para determinar si x divide por y de forma exacta y la respuesta correcta, SÍ o NO , según corresponda. Algunos de los problemas más importantes en matemáticas son indecidibles , por ejemplo, el problema de la parada .

El campo de la teoría de la complejidad computacional clasifica los problemas de decisión decidibles según su dificultad de resolución. En este contexto, la "dificultad" se describe en términos de los recursos computacionales necesarios para el algoritmo más eficiente en un problema determinado. Por otro lado, el campo de la teoría de la recursión 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 el lenguaje formal de todas las entradas para las cuales la salida (la respuesta a la pregunta de sí o no sobre una entrada dada) es SÍ . ^{[ notas 1 ]}

• Estas entradas pueden ser números naturales, pero también pueden ser valores de otro tipo, como cadenas binarias o cadenas sobre algún otro alfabeto .

• Por ejemplo, si cada entrada puede ser codificada por el alfabeto${\displaystyle \{0,1\}}$, entonces un problema de decisión es un subconjunto${\displaystyle L\subseteq \{0,1\}^{*}}$. ^{[ nota 1 ]}

• Por ejemplo, utilizando una codificación como la numeración de Gödel , cualquier cadena de caracteres puede codificarse como un número natural, lo que permite definir un problema de decisión como un subconjunto de los números naturales. Por lo tanto, el procedimiento de decisión consiste en calcular la función característica de un subconjunto de los números naturales.

Un ejemplo clásico de problema de decisión decidible es el conjunto de los números primos. Es posible determinar eficazmente si un número natural dado es primo probando todos los posibles factores no triviales. Si bien se conocen procedimientos mucho más eficientes para comprobar la primalidad , la existencia de cualquier procedimiento eficaz es suficiente para establecer la decidibilidad.

• Un problema de decisión es decidible o efectivamente resoluble si el conjunto de entradas para las cuales la respuesta es SÍ es un conjunto recursivo . ^{[ notas 2 ]}
• Un problema de decisión es parcialmente decidible , semidecidible , resoluble o demostrable si el conjunto de entradas para las cuales la respuesta es SÍ es un conjunto recursivamente enumerable .

Los problemas que no son decidibles son indecidibles , lo que significa que no es posible crear un algoritmo (eficiente o no) que los resuelva. El problema de la parada es un importante problema de decisión indecidible; para más ejemplos, consulte la lista de problemas indecidibles .

Los problemas de decisión pueden ordenarse según su reducibilidad de muchos a uno y relacionarse con reducciones factibles, como las reducciones en tiempo polinomial . Se dice que un problema de decisión P es completo para un conjunto de problemas de decisión S si P pertenece a S y cada problema en S puede reducirse 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 booleana es 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 funciones , cuyas respuestas pueden ser más complejas que un simple SÍ o NO . Un ejemplo de problema de funciones sería: "Dados dos números x e y , ¿cuánto es x dividido entre y ?".

Un problema de función consiste en una función parcial f ; el "problema" informal consiste en calcular los valores de f en las entradas para las que está definida.

Todo problema de función puede transformarse 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 resoluble, 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 polinomial (en cuyo caso el tiempo de ejecución se calcula como una función solo de x ). La función f ( x ) = 2x ^tiene esta propiedad.

Todo problema de decisión puede transformarse en un problema funcional que consiste en calcular la función característica del conjunto asociado. Si esta función es computable, entonces el problema de decisión asociado es decidible. Sin embargo, esta reducción es más flexible que la reducción estándar utilizada en complejidad computacional (a veces denominada reducción de muchos a 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 de computación típicos.

A diferencia de los problemas de decisión, en los que solo hay una respuesta correcta para cada entrada, los problemas de optimización se centran en encontrar la mejor respuesta para una entrada específica. Los problemas de optimización surgen de forma natural en muchas aplicaciones, como el problema del viajante y numerosas cuestiones de programación lineal .

Los problemas de función y optimización suelen transformarse en problemas de decisión al considerar 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 o el problema de optimización original se puede resolver solucionando su problema de decisión asociado. Por ejemplo, en el problema del viajante, el problema de optimización consiste en generar un recorrido con el menor peso posible. El problema de decisión asociado es: para cada N , determinar si el grafo contiene algún recorrido con un peso menor que N. Al responder repetidamente a este problema de decisión, es posible encontrar el recorrido con el menor peso posible.

Debido a que la teoría de los problemas de decisión está muy desarrollada, la investigación en teoría de la complejidad se ha centrado típicamente en 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 operativa .

• TODO (complejidad)
• Problema computacional
• Problema de conteo (complejidad)
• Decidibilidad (lógica) – para el problema de decidir si una fórmula es consecuencia de una teoría lógica .
• Lenguaje formal
• Problema de búsqueda
• Problema verbal (matemáticas)

• Kozen, DC (2012). Autómatas y Computabilidad . Saltador. ISBN 978-1-4612-1844-9.
• Hartley, Rogers Jr. (1987). La teoría de las funciones recursivas y la computabilidad efectiva . MIT Press. ISBN 978-0-262-68052-3.
• Sipser, M. (2020). Introducción a la teoría de la computación . Cengage Learning. ISBN 978-0-357-67058-3.
• Soare, Robert I. (1987). Conjuntos y grados recursivamente enumerables . Springer. ISBN 0-387-15299-7.
• Kroening, Daniel ; Strichman, Ofer (23 de mayo de 2008). Procedimientos de decisión . Saltador. ISBN 978-3-540-74104-6.
• Bradley, Aaron; Manna, Zohar (3 de septiembre de 2007). El cálculo de la computación . Springer. ISBN 978-3-540-74112-1.