Problema computacional

En informática teórica , un problema es aquel que pide una solución en términos de un algoritmo . Por ejemplo, el problema de factorizar

"Dado un entero positivo n , encuentra un factor primo no trivial de n ."

Es un problema computacional que tiene solución, ya que existen muchos algoritmos conocidos de factorización de enteros . 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 mapee instancias a soluciones. Por ejemplo, en el problema de factorización , las instancias son los 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 la parada . Los problemas computacionales son uno de los principales objetos de estudio en la informática teórica.

A menudo, no solo interesa la mera existencia de un algoritmo, sino también su eficiencia. El campo de la teoría de la complejidad computacional aborda estas cuestiones determinando la cantidad de recursos ( complejidad computacional ) que requiere la resolución de un problema dado y explicando por qué algunos problemas son intratables o indecidibles . Los problemas computacionales resolubles pertenecen a clases de complejidad que definen de forma general los recursos (por ejemplo, tiempo, espacio/memoria, energía, profundidad del circuito) necesarios para calcularlos (resolverlos) con diversas máquinas abstractas . Por ejemplo, las clases de complejidad

• P , problemas que consumen tiempo polinomial para máquinas clásicas deterministas
• BPP , problemas que consumen tiempo polinomial para máquinas clásicas probabilísticas (por ejemplo, computadoras con generadores de números aleatorios).
• BQP , problemas que consumen tiempo polinomial para máquinas cuánticas probabilísticas.

Tanto las instancias como las soluciones se representan mediante cadenas binarias , concretamente elementos de {0, 1} ^* . ^{[ a ]} ​​Por ejemplo, los números naturales suelen representarse como cadenas binarias utilizando 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.

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 apropiado 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 grafo G , determine si cada conjunto independiente en G tiene un tamaño como máximo de 5, o si G tiene un conjunto independiente de tamaño al menos 10."

En este caso, las instancias válidas son aquellos grafos 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 promesas desempeñan un papel importante en varias áreas de complejidad computacional , incluyendo la dificultad de aproximación , la comprobación de propiedades y los sistemas de prueba interactivos .

• Computación lateral , enfoques alternativos para resolver problemas computacionalmente.
• Modelo de computación
• Problema transcomputacional

• Even, Shimon ; Selman, Alan L.; Yacobi, Yacov (1984), "La complejidad de los problemas de promesas con aplicaciones a la criptografía de clave pública", Information and Control , 61 (2): 159–173 , doi : 10.1016/S0019-9958(84)80056-X.
• Goldreich, Oded (2008), Complejidad computacional: una perspectiva conceptual , Cambridge University Press , ISBN 978-0-521-88473-0.
• Goldreich, Oded ; Wigderson, Avi (2008), "IV.20 Complejidad computacional", en Gowers, Timothy ; Barrow-Green, June; Leader, Imre (eds.), The Princeton Companion to Mathematics , Princeton University Press, pp. 575–604 , ISBN  978-0-691-11880-2.