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 que se puede plantear como una pregunta de sí o no de los valores de entrada. Un ejemplo de un problema de decisión es decidir si un número natural dado es primo . Otro es el problema "dados dos números x e y , ¿ 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.por ese problema Un procedimiento de decisión para el problema de decisión "dados dos números x e y , ¿ x divide 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í', 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 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 en un conjunto infinito de entradas. Es tradicional definir el problema de decisión como el conjunto de posibles insumos junto con el conjunto de insumos para los cuales la respuesta es afirmativa . [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 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.
