En la teoría de Computability y la teoría de complejidad de cómputo, un problema de decisión del es una pregunta en un cierto sistema formal con una sí-o-ninguna respuesta, dependiendo de los valores de algunos parámetros de la entrada. Por ejemplo, el " del problema; ¿el dado x de dos números y el y, el x divide uniformemente el y ? " es un problema de decisión. La respuesta puede estar “sí” o “no”, y depende de los valores del x y del y .

Los problemas de decisión son estrechamente vinculados a los problemas de la función, que pueden tener las respuestas que son más complejas que simple “sí” o “no”. Un problema correspondiente de la función es " ¿el dado x de dos números y el y, cuáles es el x dividido por el y ? ". Él también se relaciona con los problemas de la optimización que se refieren a encontrar la mejor respuesta del a un problema particular.

Un método para solucionar un problema de decisión dado bajo la forma de algoritmo se llama un procedimiento de la decisión del para ese problema. Un procedimiento de la decisión para el " del problema de decisión; ¿el dado x de dos números y el y, el x divide uniformemente el y ? " daría los pasos para determinar si el x divide uniformemente el y, dado el x y el y . Un tal algoritmo es la división larga, enseñada a muchos alumnos. Si el resto es cero la respuesta producida está “sí”, si no está “no”. Un problema de decisión que se puede solucionar por un algoritmo, tal como este ejemplo, se llama el decidible.

El campo de la complejidad de cómputo categoriza problemas de decisión decidibles por cómo es difícil son solucionar. " Difficult", en este sentido, se describe en términos de recursos de cómputo necesarios por el algoritmo más eficiente para cierto problema. El campo de la teoría de la repetición, mientras tanto, categoriza problemas de decisión undecidable por el grado de Turing, que es una medida del noncomputability inherente en cualquier solución.

La investigación en teoría del computability se ha centrado típicamente en problemas de decisión. Según lo explicado en la equivalencia de la sección con los problemas de la función abajo, no hay pérdida de generalidad.

Definición

Un problema de decisión del es cualquier arbitrario sí-o-ninguna pregunta sobre un sistema infinito de entradas. Debido a esto, es tradicional definir el problema de decisión equivalente como: el sistema de las entradas para las cuales el problema vuelve el sí .

Estas entradas pueden ser números naturales, pero también otros valores de una cierta otra clase, tales como secuencias de un lenguaje formal . Usar una cierta codificación, tal como Gödel numera que las secuencias se pueden codificar como números naturales. Así, un problema de decisión expresado informal en términos de lenguaje formal es también equivalente a un sistema de los números naturales . Para mantener la definición formal simple, se expresa en términos de subconjuntos de los números naturales.

Formalmente, un problema de decisión del es un subconjunto de los números naturales. El problema informal correspondiente es el de decidir a si un número dado está en el sistema.

Un A del problema de decisión se llama el decidible o el con eficacia soluble si el A es un sistema recurrente . Un problema se llama el parcialmente decidible, el semidecidable, el soluble, o el demostrable si el A es un sistema enumerable recurrentemente. Los problemas parcialmente decidibles y cualquier otro problema que no sean decidibles se llaman el undecidable.

Ejemplos

Un ejemplo clásico de un problema de decisión decidible es el sistema de números primeros. Es posible decidir con eficacia a si un número natural dado es primero probando cada factor no trivial posible. Aunque métodos mucho más eficientes de la prueba de Primality se sepan, la existencia de cualquier método eficaz es bastante para establecer decidibilidad.

Los problemas de decisión undecidable importantes incluyen el problema que para ; para más, ver la lista de los problemas undecidable . En la complejidad de cómputo, los problemas de decisión que son el completo se utilizan para caracterizar clases de la complejidad de problemas de decisión. Los ejemplos importantes incluyen el problema boleano y varios del satisfiability de sus variantes, junto con el sin señas y el problema dirigido del reachability.

Historia

El Entscheidungsproblem del, alemán para el " Decisión-problem", se atribuye al David Hilbert : " En la conferencia de 1928 Hilbert hizo sus preguntas absolutamente exactas. ¿Primero, era el segundo completo del de las matemáticas…, era el constante de las matemáticas… y en tercer lugar, era el de las matemáticas decidible? Por esto él significó, allí existió un método definido que podrían, en principio ser aplicado a cualquier aserción, y que fue garantizado para producir una decisión correcta encendido si esa aserción era true" (Hodges, P. Hilbert creyó ese " en matemáticas no hay significado de Ignorabimus '(Hodges, P. 91ff) “que no sabremos”. Ver el David Hilbert y el problema que para para más.

¡Equivalencia con el problems< de la función! -- Esta sección se liga del problema de decisión -->

Un problema de la función consiste en un parcial f de la función ; el " informal; problem" es computar los valores del f en las entradas para las cuales se define.

Cada problema de la función se puede dar vuelta en un problema de decisión; el problema de decisión es apenas el gráfico de la función asociada. (El gráfico de un f de la función es el sistema de los pares ( x, y ) tales que el f ( x ) = el y .) Si este problema de decisión fuera con eficacia soluble entonces el problema de la función estaría también. Esta reducción no respeta complejidad de cómputo, sin embargo. Por ejemplo, es posible que el gráfico de una función sea decidible en tiempo polinómico (en este caso el tiempo en marcha se computa en función de los pares ( x, y )) cuando la función no es computable en tiempo polinómico (en este caso el tiempo en marcha se computa en función del x solamente). El f ( x ) de la función = el x del ^{del 2 tiene esta característica.}

Cada problema de decisión se puede convertir en el problema de la función de computar la función característica del sistema 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 usada en la complejidad de cómputo (a veces llamada polinómico-tiempo mucho-uno reducción); por ejemplo, la complejidad de las funciones características de un problema NP-completo y de su complemento Co-NP-completo es exactamente igual aunque los problemas de decisión subyacentes no se pueden considerar equivalentes en algunos modelos típicos del cómputo.