In theoretical computer science, a computational problem is a problem that a computer might be able to solve, or a question that a computer may be able to answer. For example, the problem of factoring is a computational problem. A computational problem can be viewed as an infinite collection of instances together with a, possibly empty, set of solutions for every instance. For example, in the factoring problem, the instances are the integers n, and solutions are prime numbersp that describe nontrivial prime factors of n. Computational problems are one of the main objects of study in theoretical computer science. The field of computational complexity theory attempts to determine the amount of resources solving a given problem will require and explain why some problems are intractable or undecidable. Computational problems belong to complexity classes that define broadly the time it takes to compute them with various abstract machines. It is typical of many problems to represent both instances and solutions by binary strings, namely elements of *. For example, numbers can be represented as binary strings using the binary encoding. For readability, we sometimes identify numbers with their binary encodings in the examples below.
Types of computational problems
A decision problem is a computational problem where the answer for every instance is either yes or no. An example of a decision problem is primality testing: A decision problem is typically represented as the set of all instances for which the answer is yes. For example, primality testing can be represented as the infinite set In a search problem, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are positive integers and the solutions are collections of primes. A search problem is represented as a relationconsisting of all the instance-solution pairs, called a search relation. For example, factoring can be represented as the relation which consist of all pairs of numbers, where p is a nontrivial prime factor of n. A counting problem asks for the number of solutions to a given search problem. For example, a counting problem associated with factoring is A counting problem can be represented by a function f from * to the nonnegative integers. For a search relation R, the counting problem associated to R is the function An optimization problem asks for finding a "best possible" solution among the set of all possible solutions to a search problem. One example is the maximum independent set problem: Optimization problems can be represented by their search relations. In a function problem a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just "yes" or "no". One of the most famous examples is the travelling salesman problem: It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
Promise problem
In computational complexity theory, it is usually implicitly assumed that any string in * represents an instance of the computational problem in question. However, sometimes not all strings * represent valid instances, and one specifies a proper subset of * as the set of "valid instances". Computational problems of this type are called promise problems. The following is an example of a promise problem: Here, the valid instances are those graphs whose maximum independent setsize is either at most 5 or at least 10. Decision promise problems are usually represented as pairs of disjoint subsets of *. The valid instances are those in Lyes ∪ Lno. Lyes and Lno represent the instances whose answer is yes and no, respectively. Promise problems play an important role in several areas of computational complexity, including hardness of approximation, property testing, and interactive proof systems.
