In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, a computational resource is a resource used by some
computational models in the solution of
computational problems.
The simplest computational resources are
computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, but many more complicated resources have been defined.
A computational problem is generally defined in terms of its action on any valid input. Examples of problems might be "given an integer ''n'', determine whether ''n'' is prime", or "given two numbers ''x'' and ''y'', calculate the product ''x''*''y''". As the inputs get bigger, the amount of computational resources needed to solve a problem will increase. Thus, the resources needed to solve a problem are described in terms of
asymptotic analysis
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing Limit (mathematics), limiting behavior.
As an illustration, suppose that we are interested in the properties of a function as becomes very larg ...
, by identifying the resources as a function of the length or size of the input. Resource usage is often partially quantified using
Big ''O'' notation.
Computational resources are useful because we can study which problems can be computed in a certain amount of each computational resource. In this way, we can determine whether
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s for solving the problem are optimal and we can make statements about an
algorithm's efficiency. The set of all of the computational problems that can be solved using a certain amount of a certain computational resource is a
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
, and relationships between different complexity classes are one of the most important topics in complexity theory.
Describing generally accessible computing equipment
The term "Computational resource" is commonly used to describe accessible computing equipment and software. See
Utility computing.
Formal quantification of computing capability
There has been some effort to formally quantify computing capability. A bounded
Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
has been used to model specific computations using the number of state transitions and alphabet size to quantify the computational effort required to solve a particular problem.
References
{{reflist, 1
Computational complexity theory