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
- "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 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. (For readability, we identify numbers with their binary encodings in the examples below.)
Read more about Computational Problem: Types of Computational Problems, Promise Problems
Famous quotes containing the word problem:
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)