En informática teórica , un problema computacional es un problema que puede resolverse mediante un algoritmo . Por ejemplo, el problema del factoring.
es un problema computacional. 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. 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 factores primos no triviales de n .
Los problemas computacionales son uno de los principales objetos de estudio de la informática teórica. El campo de la teoría de la complejidad computacional intenta determinar la cantidad de recursos ( complejidad computacional ) que requerirá la resolución de un problema determinado y explicar por qué algunos problemas son intratables o indecidibles . Los problemas computacionales 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 están representadas por cadenas binarias , es decir, elementos de {0, 1} * . [a] Por ejemplo, los números naturales generalmente se representan como cadenas binarias usando codificación binaria . Esto es importante ya que la complejidad se expresa en 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 problema de decisión son las pruebas de primalidad :
Un problema de decisión generalmente se representa como el conjunto de todos los casos para los cuales 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 en cadena de) números enteros positivos y las soluciones son (representaciones en cadena de) colecciones de números primos.
Un problema de búsqueda se representa como una relación que consta de todos los pares instancia-solución, llamada relación de búsqueda . Por ejemplo, la factorización se puede representar como la relación
que constan de todos los pares de números ( n , p ), donde p es un factor primo de n .
Un problema de conteo pregunta por el número de soluciones a un problema de búsqueda determinado. 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 requiere encontrar la "mejor solución posible" entre el conjunto de todas las soluciones posibles 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 solo "sí" o "no". Uno de los ejemplos más famosos es el problema del viajante :
Es un problema NP-difícil en optimización combinatoria , importante en investigación de operaciones e informática teórica .
En la teoría de la complejidad computacional , generalmente se supone 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 una 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í, los casos válidos son aquellos gráficos cuyo tamaño máximo de conjunto independiente es como máximo 5 o al menos 10.
Los problemas de promesa de decisión generalmente se representan como pares de subconjuntos disjuntos ( L sí , L no ) de {0, 1} * . Los casos válidos son aquellos en L sí ∪ L no . L sí y L no representan las instancias cuya respuesta es sí y no , respectivamente.
Los problemas de promesa desempeñan un papel importante en varias áreas de complejidad computacional , incluida la dureza de aproximación , las pruebas de propiedades y los sistemas de prueba interactivos .