Computational problem
Encyclopedia
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
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.)
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 (string representations of) positive integers and the solutions are (string representations of) collections of primes.
A search problem is represented as a relation
over consisting of all the instance-solution pairs, called a search relation. For example, primality can be represented as the relation
which consist of all pairs of numbers (n, p), 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, the counting problem associated with primality is
A counting problem can be represented by a function f from {0, 1}* to the nonnegative integers. For a search relation R, the counting problem associated to R is the function
An optimization problem
asks for finding the "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.
, it is usually implicitly assumed that any string in {0, 1}* represents an instance of the computational problem in question. However, sometimes not all strings {0, 1}* represent valid instances, and one specifies a proper subset of {0, 1}* as the set of "valid instances". Computational problems of this type are called promise problem
s.
The following is an example of a (decision) promise problem:
Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.
Decision promise problems are usually represented as pairs of disjoint subsets (Lyes, Lno) of {0, 1}*. 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 system
s.
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
, a computational problem is a mathematical object
Mathematical object
In mathematics and the philosophy of mathematics, a mathematical object is an abstract object arising in mathematics.Commonly encountered mathematical objects include numbers, permutations, partitions, matrices, sets, functions, and relations...
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
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*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
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
, 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.)
Types of computational problems
A decision problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is 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:
- "Given a positive integer n, determine if n is prime."
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
- L = {2, 3, 5, 7, 11, ...}
In a search problem
Search problem
In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation...
, the answers can be arbitrary strings. For example, factoring is a search problem where the instances are (string representations of) positive integers and the solutions are (string representations of) collections of primes.
A search problem is represented as a relation
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
over consisting of all the instance-solution pairs, called a search relation. For example, primality can be represented as the relation
- R = {(4, 2), (6, 2), (6, 3), (8, 2), (8, 4), (9, 3), ...}
which consist of all pairs of numbers (n, p), 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, the counting problem associated with primality is
- "Given a positive integer n, count the number of nontrivial prime factors of n."
A counting problem can be represented by a function f from {0, 1}* to the nonnegative integers. For a search relation R, the counting problem associated to R is the function
- fR(x) = |{y: (x, y) ∈ R}|.
An optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
asks for finding the "best possible" solution among the set of all possible solutions to a search problem. One example is the maximum independent set problem:
- "Given a graph G, find an independent setIndependent set (graph theory)In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
of G of maximum size."
Optimization problems can be represented by their search relations.
Promise problems
In computational complexity theoryComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, it is usually implicitly assumed that any string in {0, 1}* represents an instance of the computational problem in question. However, sometimes not all strings {0, 1}* represent valid instances, and one specifies a proper subset of {0, 1}* as the set of "valid instances". Computational problems of this type are called promise problem
Promise problem
In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs. Unlike decision problems, the yes instances and no instances do not exhaust the set of all inputs...
s.
The following is an example of a (decision) promise problem:
- "Given a graph G, determine if every independent set in G has size at most 5, or G has an independent set of size at least 10."
Here, the valid instances are those graphs whose maximum independent set size is either at most 5 or at least 10.
Decision promise problems are usually represented as pairs of disjoint subsets (Lyes, Lno) of {0, 1}*. 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
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
, including hardness of approximation
Hardness of approximation
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. It complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can...
, property testing
Property testing
In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem...
, and interactive proof system
Interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
s.