Problema computacional

Problema computacional
Un problema computacional constituye una pregunta a ser respondida, teniendo generalmente varios parámetros, o variables libres, cuyos valores no se han especificado. Unproblema se describe mediante:
1. Una descripción general de todos sus parámetros (pueden ser de entrada o de salida).
2. Una sentencia que describa las propiedades que la respuesta, o la solución, debecumplir.
Una instancia de un problema se obtiene cuando se especifican valores particulares para todos los parámetros del problema. Por ejemplo, consideremos el problema del test de primalidad. Lainstancia es un número (e.g. 15) y la solución es "sí" si el número es primo, y "no" en caso contrario. Visto de otra manera, la instancia es una entrada particular del problema, y la solución es lasalida correspondiente para la entrada dada.
Solución al problema computacional
Algoritmo a tiempo polinomial.- En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual seobtiene una solución al problema) es menor que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dichoproblema se puede resolver en un tiempo polinómico.
Por ejemplo, si determinar el camino óptimo que debe recorrer un cartero que pasa por N casas necesita menos de 50N2+N segundos, entonces el problemaes resoluble en un "tiempo polinómico".
Algoritmo a tiempo polinomial.- En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de losproblemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n.
En términos de DTIME,

Se sabe que
P ⊆ NP ⊆ PSPACE ⊆EXPTIME ⊆ EXPSPACE
y por el teorema de la jerarquía temporal:
P ⊂ EXPTIME
de manera que al menos una de las inclusiones de la primera línea debe ser estricta (se piensa que todas esas inclusiones...