Computational problem
From Wikipedia, the free encyclopedia
In theoretical computer science, a computational problem is a mathematical object representing a question that computers might want to solve. For example, "given any number x, determine whether x is prime" is a computational problem. Computational problems are one of the main objects of study in theoretical computer science, because nearly any task one would want to accomplish is an example of a computational problem. In the field of algorithms, we study methods of solving computational problems; in the complementary field of computational complexity theory, we organize computational problems based on how difficult they are to solve.
[edit] Problems and instances
A computational problem encodes a general problem, independent of its specific input. A problem with a specific set of inputs is called an instance. For example, "Given any two numbers x and y, find the sum of x and y" is a computational problem. A specific instance of that computational problem would be "What is the sum of 13 and 28?".
[edit] Types of computational problems
Computational problems are organized in many different ways. They can be organized by how they are defined, and by how many computational resources are needed to compute an answer. Computational problems that intuitively look very similar can vary wildly in the amount of resources needed to compute them, and some computational problems are noncomputable, meaning that no possible algorithm could solve every instance.
A computational problem which only returns a yes-or-no answer is called a decision problem. Examples of decision problems include "given an integer n, determine whether n is prime" and "given two numbers x and y, determine whether x evenly divides y". Decision problems are often used in computational complexity theory, because they are easier to study than other problems.
Computational problems that are not restricted to yes-or-no answers are called function problems. Examples of function problems include "given an integer n, list the prime factorization of n" and "given two numbers x and y, output x divided by y".
