En informática teórica , un problema computacional es aquel que pide una solución en términos de un algoritmo . Por ejemplo, el problema de factorización
es un problema computacional que tiene una solución, ya que existen muchos algoritmos de factorización de números enteros conocidos . Un problema computacional puede verse como un conjunto de instancias o casos junto con un conjunto, posiblemente vacío, de soluciones para cada instancia/caso. La pregunta entonces es si existe un algoritmo que asigne instancias a soluciones. Por ejemplo, en el problema de factorización , las instancias son los números enteros n , y las soluciones son números primos p que son los factores primos no triviales de n . Un ejemplo de un problema computacional sin solución es el problema de Halting . Los problemas computacionales son uno de los principales objetos de estudio en la informática teórica.
A menudo, no solo nos interesa la mera existencia de un algoritmo, sino también la eficiencia que puede tener. El campo de la teoría de la complejidad computacional aborda estas cuestiones determinando la cantidad de recursos ( complejidad computacional ) que requerirá la solución de un problema determinado y explicando por qué algunos problemas son intratables o indecidibles . Los problemas computacionales solucionables pertenecen a clases de complejidad que definen ampliamente los recursos (por ejemplo, tiempo, espacio/memoria, energía, profundidad del circuito) que se necesitan para calcularlos (resolverlos) con varias máquinas abstractas . Por ejemplo, las clases de complejidad
Tanto las instancias como las soluciones se representan mediante cadenas binarias , es decir, elementos de {0, 1} * . [a] Por ejemplo, los números naturales suelen representarse como cadenas binarias mediante codificación binaria . Esto es importante ya que la complejidad se expresa como una función de la longitud de la representación de entrada.
Un problema de decisión es un problema computacional en el que la respuesta para cada caso es sí o no. Un ejemplo de un problema de decisión es la prueba de primalidad :
Un problema de decisión se representa típicamente como el conjunto de todas las instancias para las que la respuesta es sí . Por ejemplo, la prueba de primalidad se puede representar como el conjunto infinito
En un problema de búsqueda , las respuestas pueden ser cadenas arbitrarias. Por ejemplo, la factorización es un problema de búsqueda en el que las instancias son (representaciones de cadenas de) números enteros positivos y las soluciones son (representaciones de cadenas de) conjuntos de números primos.
Un problema de búsqueda se representa como una relación que consta de todos los pares de instancia-solución, llamada relación de búsqueda . Por ejemplo, la factorización se puede representar como la relación
que consisten en todos los pares de números ( n , p ), donde p es un factor primo de n .
Un problema de conteo pide la cantidad de soluciones a un problema de búsqueda dado. Por ejemplo, un problema de conteo asociado con la factorización es
Un problema de conteo se puede representar mediante una función f desde {0, 1} * hasta los números enteros no negativos. Para una relación de búsqueda R , el problema de conteo asociado a R es la función
Un problema de optimización exige encontrar la "mejor solución posible" entre el conjunto de todas las posibles soluciones a un problema de búsqueda. Un ejemplo es el problema del conjunto máximo independiente :
Los problemas de optimización están representados por su función objetivo y sus restricciones.
En un problema de función se espera una única salida (de una función total ) para cada entrada, pero la salida es más compleja que la de un problema de decisión , es decir, no es simplemente "sí" o "no". Uno de los ejemplos más famosos es el problema del viajante :
Es un problema NP-hard en optimización combinatoria , importante en investigación de operaciones y ciencia informática teórica .
En la teoría de la complejidad computacional , se suele asumir implícitamente que cualquier cadena en {0, 1} * representa una instancia del problema computacional en cuestión. Sin embargo, a veces no todas las cadenas {0, 1} * representan instancias válidas, y se especifica un subconjunto adecuado de {0, 1} * como el conjunto de "instancias válidas". Los problemas computacionales de este tipo se denominan problemas de promesa .
El siguiente es un ejemplo de un problema de promesa (de decisión):
Aquí, las instancias válidas son aquellos gráficos cuyo tamaño máximo de conjunto independiente es como máximo 5 o como mínimo 10.
Los problemas de promesa de decisión se representan generalmente como pares de subconjuntos disjuntos ( L sí , L no ) de {0, 1} * . Las instancias válidas son aquellas en L sí ∪ L no . L sí y L no representan las instancias cuya respuesta es sí y no , respectivamente.
Los problemas de promesa juegan un papel importante en varias áreas de complejidad computacional , incluida la dificultad de aproximación , las pruebas de propiedades y los sistemas de prueba interactivos .