Computational resource - Revision history

Karl Jones: /* See also */

2016-09-20T17:22:05Z

‎See also

Karl Jones at 17:21, 20 September 2016

2016-09-20T17:21:45Z

Karl Jones: Created page with "In computational complexity theory, a '''computational resource''' is a resource used by some computational models in the solution of Computation..."

2016-09-20T17:20:17Z

Created page with "In computational complexity theory, a '''computational resource''' is a resource used by some computational models in the solution of Computation..."

New page

In [[computational complexity theory]], a '''computational resource''' is a resource used by some [[Computational model|computational models]] in the solution of [[Computational problem|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, 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 algorithms 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]], and relationships between different complexity classes are one of the most important topics in [[complexity theory]].

== See also ==

* [[Complexity theory]]
* [[Computational complexity theory]]
* [[Computational model]]
* [[Computational problem]]

== External links ==

* [https://en.wikipedia.org/wiki/Computational_resource Computational resource] @ Wikipedia

[[Category:Complexity]]
[[Category:Computing]]

@@ Line 15: / Line 15: @@
 * [[Algorithm]]
 * [[Algorithmic efficiency]]
 * [[Complexity theory]]
 * [[Computational complexity theory]]

@@ Line 7: / Line 7: @@
 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, 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 algorithms for solving the problem are optimal and we can make statements about an algorithm's efficiency.
+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|algorithms]] for solving the problem are optimal and we can make statements about an [[Algorithmic efficiency|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]], and relationships between different complexity classes are one of the most important topics in [[complexity theory]].
@@ Line 13: / Line 13: @@
 == See also ==
 * [[Complexity theory]]
 * [[Computational complexity theory]]