Problema de decisión

A problema de la decisión sólo tiene dos productos posibles (Sí. o no) en cualquier entrada.

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 se puede plantear como una pregunta de sí o no de 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 x e y, ¿x divide uniformemente a y?& #34;. 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 y?" daría los pasos para determinar si x divide uniformemente a y. 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 ser resuelto por un algoritmo se llama 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 de las matemáticas son indecidibles.

El campo de la complejidad computacional categoriza los problemas de decisión decidibles por lo difíciles que son 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 recursión categoriza 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.

Definición

Un problema de decisión es una pregunta de sí o no en 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 cuales la respuesta es sí.

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 que 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, a través del cual un problema de decisión puede definirse 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 los números naturales.

Ejemplos

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 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 efectivo es suficiente para establecer la decidibilidad.

Decidibilidad

Un problema de decisión es decidible o efectivamente solucionable si el conjunto de entradas (o números naturales) para el que la respuesta es sí es un conjunto recursivo. Un problema es parcialmente decidible, semidecidible, soluble o probable 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 ver más ejemplos, consulte la lista de problemas indecidibles.

Problemas completos

Los problemas de decisión se pueden ordenar de acuerdo con la reducibilidad de muchos a uno y se pueden relacionar 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 todos los problemas en S se pueden 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 es completo para la clase NP de problemas de decisión bajo reducibilidad en tiempo polinomial.

Problemas de funcionamiento

Los problemas de decisión están estrechamente relacionados con los problemas de función, cuyas respuestas pueden ser 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 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á 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 polinomial (en cuyo caso el tiempo de ejecución se calcula como una función de x solo). La función f(x) = 2^x tiene esta propiedad.

Todo problema de decisión se puede convertir en el 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 la complejidad computacional (a veces llamada 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 típicos de computación.

Problemas de optimizació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 para una entrada en particular. Los problemas de optimización surgen de forma natural en muchas aplicaciones, como el problema del viajante de comercio y muchas cuestiones de programación lineal.

Existen técnicas estándar para transformar problemas de función y optimización en problemas de decisión. Por ejemplo, en el problema del viajante de comercio, el problema de optimización consiste en 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 peso menor que N. Al responder repetidamente el 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 la teoría de la complejidad generalmente se ha centrado en los problemas de decisión. Los problemas de optimización en sí siguen siendo de interés en la teoría de la computabilidad, así como en campos como la investigación de operaciones.