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:
- "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, 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
- R = {(4, 2), (6, 2), (6, 3), (8, 2), (9, 3), (10, 2), (10, 5)...}
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 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 set of G of maximum size."
Optimization problems can be represented by their search relations.
Read more about this topic: Computational Problem
Famous quotes containing the words types of, types and/or problems:
“Science is intimately integrated with the whole social structure and cultural tradition. They mutually support one other—only in certain types of society can science flourish, and conversely without a continuous and healthy development and application of science such a society cannot function properly.”
—Talcott Parsons (1902–1979)
“... there are two types of happiness and I have chosen that of the murderers. For I am happy. There was a time when I thought I had reached the limit of distress. Beyond that limit, there is a sterile and magnificent happiness.”
—Albert Camus (1913–1960)
“I was a wonderful parent before I had children. I was an expert on why everyone else was having problems with theirs. Then I had three of my own.”
—Adele Faber (20th century)