Difference between revisions of "Computational problem"
Karl Jones (Talk | contribs) (→See also) |
Karl Jones (Talk | contribs) |
||
| Line 7: | Line 7: | ||
The field of [[Algorithm|algorithms]] studies methods of solving computational problems efficiently. | The field of [[Algorithm|algorithms]] studies methods of solving computational problems efficiently. | ||
| − | The complementary field of [[computational complexity]] attempts to explain why certain computational problems are intractable for computers. | + | The complementary field of [[computational complexity theory]] attempts to explain why certain computational problems are intractable for computers. |
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. For example in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n. | A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. For example in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n. | ||
| Line 16: | Line 16: | ||
* [[Computation]] | * [[Computation]] | ||
| − | * [[Computational complexity]] | + | * [[Computational complexity theory]] |
* [[Mathematical object]] | * [[Mathematical object]] | ||
* [[Theoretical computer science]] | * [[Theoretical computer science]] | ||
Revision as of 05:18, 21 August 2015
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might be able to solve.
For example, the problem of factoring "Given a positive integer n, find a nontrivial prime factor of n." is a computational problem.
Computational problems are one of the main objects of study in theoretical computer science.
The field of algorithms studies methods of solving computational problems efficiently.
The complementary field of computational complexity theory attempts to explain why certain computational problems are intractable for computers.
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. For example in the factoring problem, the instances are the integers n, and solutions are prime numbers p that describe nontrivial prime factors of n.
It is conventional to represent both instances and solutions by binary strings, namely elements of {0, 1}*. For example, numbers can be represented as binary strings using the binary encoding.
See also
External links
- Computational problem @ Wikipedia
