Computational resource
Encyclopedia
In computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, a computational resource is a resource used by some computational model
Computational model
A computational model is a mathematical model in computational science that requires extensive computational resources to study the behavior of a complex system by computer simulation. The system under study is often a complex nonlinear system for which simple, intuitive analytical solutions are...

s in the solution of computational problem
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...

s.

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
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...

, by identifying the resources as a function of the length or size of the input.

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
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s for solving the problem are optimal and we can make statements about an algorithm's efficiency
Algorithmic efficiency
In computer science, efficiency is used to describe properties of an algorithm relating to how much of various types of resources it consumes. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process, where the goal is to reduce...

. 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
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...

, 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
Utility computing
Utility computing is the packaging of computing resources, such as computation, storage and services, as a metered service similar to a traditional public utility...

.

Formal quantification of computing capability

There has been some effort to formally quantify computing capability. A bounded Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...

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.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK