Problema computacional

En ciencia computacional teórica, un problema computacional o problema abstracto es una relación entre un conjunto de instancias y un conjunto de soluciones. Un problema abstracto permite establecer formalmente la relación deseada entre cada instancia del problema y su correspondiente solución. Una solución algorítmica a un problema abstracto consiste de un algoritmo que por cada instancia del problema calcula al menos una solución correspondiente –en caso de haberla– o expide un certificado de que no existe solución alguna. Un problema abstracto se convierte en un problema concreto cuando las instancias y soluciones están codificadas en forma de lenguajes formales.

Los problemas abstractos suelen definirse en dos partes: en la primera se describe al conjunto de instancias y en la segunda se describe la solución esperada para cada instancia. Por ejemplo, el problema de ordenación de números enteros se suele definir como sigue:
Instancia: Una sucesión finita de números enteros 
Solución: Una permutación  de la sucesión de entrada tal que 
Aquí tanto el conjunto de instancias y el de soluciones es el mismo, pues se trata del conjunto de todas las sucesiones finitas de números enteros. La relación que hay entre ellos asigna a cada sucesión  la única permutación  tal que . Por ejemplo,  tiene como solución a . Una solución algorítmica al problema de ordenamiento es el ordenamiento de burbuja porque este algoritmo produce una solución como salida cada vez que se le suministra una instancia como entrada.

Tipos de problemas computacionales 

En un problema de decisión cada instancia tiene asociada exactamente una solución "sí" o "no". Los problemas de decisión quedan completamente determinados por el conjunto  de instancias que tienen asociada la solución "sí". Por ejemplo, el problema de decidir si una gráfica tiene o no un ciclo Hamiltoniano queda completamente determinado su conjunto de soluciones "sí":Con esta representación el problema equivale a preguntar si una instancia  pertenece o no al conjunto . En general, los problemas de decisión siempre equivalen a decidir la proposición  donde  es el conjunto de instancias con solución "sí". Una solución algorítmica para un problema de decisión es un algoritmo que calcula la función característica de  o equivalente: 

En los problemas de búsqueda la relación entre el conjunto de instancias y el de soluciones queda determinado por un predicado lógico  que determina si  es una solución de . Dada una instancia  el problema consiste en encontrar, si es que existe, una solución  de . Es decir, buscar el elemento  que haga verdadera la proposición . Cuando se fija el valor de  y la solución es única, se dice que es un problema matemático. Por ejemplo, el problema de factorización de un número entero  consiste en encontrar un factor no trivial de ; es decir, número entero  diferente de 1 y de  tal que  divida exactamente a . En símbolos

Esta fórmula simplemente está preguntando la existencia de un factor no trivial de . Una solución algorítmica a un problema de búsqueda viene dador por un algoritmo  tal que  es verdadera siempre y cuando exista solución para , es decir,  siempre calcula una solución si es que esta existe. En el caso del problema de la factorización de enteros se cuenta con el algoritmo de la división por tentativa.

En un problema de optimización no solo se busca una solución, sino que se busca "la mejor" de todas. Cada problema de optimización puede concebirse como un problema de búsqueda y una función , comúnmente conocida como función objetivo, que determina la calidad de las soluciones. El problema de optimización (que a su vez es de búsqueda) consiste en encontrar la solución maximice o minimice el valor de . Por ejemplo, el problema del viajante no solamente exige determinar si una gráfica tiene o no un ciclo hamiltoniano, sino que además pregunta cuál es el ciclo hamiltoniano más corto. En este caso el problema de búsqueda subyacente es encontrar un ciclo hamiltoniano cualquiera y la función objetivo mide la distancia recorrida por ese ciclo.

Referencias 

 Gómez Navas Lozano, Ricardo Iván, Gómez Navas Chapa Leonardo, Introducción a las Ciencias Sociales, McGraw Hill, China, 2011
 

Informática teórica
Computabilidad