En informática teórica , un problema computacional es un problema que una computadora podría resolver o una pregunta que una computadora podría responder. Por ejemplo, el problema de factorizar
- "Dado un número entero positivo n , encuentre un factor primo no trivial de n ".
es un problema computacional. Un problema computacional puede verse como una colección infinita de instancias o casos junto con un conjunto de soluciones , posiblemente vacío, 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 describen factores primos no triviales de n .
Los problemas computacionales son uno de los principales objetos de estudio en 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á resolver un problema dado 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, máquinas clásicas o cuánticas ).
Es típico de muchos problemas representar tanto instancias como soluciones mediante cadenas binarias , es decir, elementos de {0, 1} * (consulte las expresiones regulares para la notación utilizada). Por ejemplo, los números se pueden representar como cadenas binarias mediante codificación binaria.
Para facilitar la lectura, a veces identificamos números con sus codificaciones binarias en los ejemplos siguientes.
Tipos
Un problema de decisión es un problema computacional donde la respuesta para cada caso es sí o no. Un ejemplo de un problema de decisión es la prueba de primalidad :
- "Dado un número entero positivo n , determine si n es primo".
Por lo general, un problema de decisión se representa como el conjunto de todas las instancias para las que la respuesta es sí . Por ejemplo, las pruebas de primalidad se pueden representar como el conjunto infinito
- L = {2, 3, 5, 7, 11, ...}
En un problema de búsqueda , las respuestas pueden ser cadenas arbitrarias. Por ejemplo, la factorización es un problema de búsqueda donde las instancias son (representaciones de cadena de) enteros positivos y las soluciones son (representaciones de 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, denominada relación de búsqueda . Por ejemplo, la factorización se puede representar como la relación
- R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5) ...}
que constan de todos los pares de números ( n , p ), donde p es un factor primo no trivial de n .
Un problema de conteo pide el número de soluciones a un problema de búsqueda dado. Por ejemplo, un problema de conteo asociado con la factorización es
- "Dado un número entero positivo n , cuente el número de factores primos no triviales de n ".
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
- f R (x) = | { y : R ( x , y )} |.
Un problema de optimización requiere encontrar una "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 :
- "Dada una gráfica G , encuentra un conjunto independiente de G de tamaño máximo".
Los problemas de optimización se pueden representar mediante sus relaciones de búsqueda.
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 :
- "Dada una lista de ciudades y las distancias entre cada par de ciudades, encuentre la ruta más corta posible que visite cada ciudad exactamente una vez y regrese a la ciudad de origen".
Es un problema NP-difícil en optimización combinatoria , importante en investigación de operaciones e informática teórica .
Promesa problema
En la teoría de la complejidad computacional , generalmente se asume 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):
- "Dado un gráfico G , determine si cada conjunto independiente en G tiene un tamaño como máximo de 5, o G tiene un conjunto independiente de tamaño de al menos 10."
Aquí, las instancias válidas son aquellas gráficas 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 generalmente se representan como pares de subconjuntos disjuntos ( L sí , L no ) de {0, 1} * . Las instancias válidas son las de L sí ∪ L no . L sí y L no representan las instancias cuya respuesta es sí y no , respectivamente.
Los problemas de promesas juegan un papel importante en varias áreas de complejidad computacional , incluida la dureza de la aproximación , las pruebas de propiedades y los sistemas de prueba interactivos .
Ver también
- Computación lateral , enfoques alternativos para la resolución de problemas computacionalmente
Referencias
- Incluso, Shimon ; Selman, Alan L .; Yacobi, Yacov (1984), "La complejidad de los problemas de promesa con aplicaciones a la criptografía de clave pública", Información y control , 61 (2): 159-173, doi : 10.1016 / S0019-9958 (84) 80056-X.
- Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective , Cambridge University Press , ISBN 978-0-521-88473-0.
- Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 Computational Complexity", en Gowers, Timothy ; Barrow-Green, junio; Líder, Imre (eds.), The Princeton Companion to Mathematics , Princeton University Press, págs. 575–604, ISBN 978-0-691-11880-2.