Recurs computacional

En la teoria de la complexitat computacional, un recurs computacional és un recurs utilisat per alguns models computacionals en la solució de problemes computacionals.

Els recursos computacionals més simples són la complexitat temporal, la cantitat de passos necessaris per a resoldre un problema, i l'espai de memòria, la cantitat d'almagasenament necessària per a resoldre el problema, pero s'han definit molts recursos més complicats.^{cita requerida}

Un problema computacional és generalment^{cita requerida} definit en térmens de la seua acció en qualsevol entrada vàlida. Eixemples de problemes podrien ser "donat un número entero n, determine si n és primer", o "daus dos números x i i, calcule el producte x * i ". A mida que les entrades aumenten, la cantitat de recursos computacionals necessaris per a resoldre un problema aumentarà. Aixina, els recursos necessaris per a resoldre un problema es descriuen en térmens d'anàlisis asintòtic, identificant els recursos en funció de la llongitut o el tamany de l'entrada. L'us de recursos a sovint es quantifica parcialment utilisant la cota superior asintòtica.

Els recursos computacionals són útils perque podem estudiar qué problemes es poden calcular en una certa cantitat de cada recurs computacional. D'esta forma, podem determinar si els algoritmes per a resoldre el problema són òptims i podem fer afirmacions sobre l'eficiència algorítmica. El conjunt de tots els problemes computacionals que es poden resoldre usant una certa cantitat d'un cert recurs computacional és una classe de complexitat, i les relacions entre diferents classes de complexitat són un dels temes més importants en la teoria de la complexitat.

Quantificació formal de la capacitat informàtica

Hi ha hagut algun esforç per a quantificar formalment la capacitat computacional. S'ha utilisat una màquina de Turing llimitada per a modelar càlculs específics usant el número de transicions d'estat i el tamany de l'alfabet per a quantificar l'esforç computacional requerit per a resoldre un problema en particular.