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 codificarse mediante el alfabeto , entonces un problema de decisión es un subconjunto . ^{[ notas 1 ]}${\displaystyle \{0,1\}}$${\displaystyle L\subseteq \{0,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 ?".

A function problem consists of a partial functionf; the informal "problem" is to compute the values of f on the inputs for which it is defined.

Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function. (The graph of a function f is the set of pairs (x,y) such that f(x) = y.) If this decision problem were effectively solvable then the function problem would be as well. This reduction does not respect computational complexity, however. For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair (x,y)) when the function is not computable in polynomial time (in which case running time is computed as a function of x alone). The function f(x) = 2^x has this property.

Every decision problem can be converted into the function problem of computing the characteristic function of the set associated to the decision problem. If this function is computable then the associated decision problem is decidable. However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial-time many-one reduction); for example, the complexity of the characteristic functions of an NP-complete problem and its co-NP-completecomplement is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.

Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding the best answer to a particular input. Optimization problems arise naturally in many applications, such as the traveling salesman problem and many questions in linear programming.

Function and optimization problems are often transformed into decision problems by considering the question of whether the output is equal to or less than or equal to a given value. This allows the complexity of the corresponding decision problem to be studied; and in many cases the original function or optimization problem can be solved by solving its corresponding decision problem. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each N, to decide whether the graph has any tour with weight less than N. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.

Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as operations research.

• ALL (complexity)
• Computational problem
• Counting problem (complexity)
• Decidability (logic)– for the problem of deciding whether a formula is a consequence of a logical theory.
• Formal language
• Search problem
• Word problem (mathematics)

• Kozen, D.C. (2012). Automata and Computability. Springer. ISBN 978-1-4612-1844-9.
• Hartley, Rogers Jr (1987). The Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 978-0-262-68052-3.
• Sipser, M. (2020). Introduction to the Theory of Computation. Cengage Learning. ISBN 978-0-357-67058-3.
• Soare, Robert I. (1987). Recursively Enumerable Sets and Degrees. Springer. ISBN 0-387-15299-7.
• Kroening, Daniel; Strichman, Ofer (23 May 2008). Decision procedures. Springer. ISBN 978-3-540-74104-6.
• Bradley, Aaron; Manna, Zohar (3 September 2007). The calculus of computation. Springer. ISBN 978-3-540-74112-1.