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:
“The wider the range of possibilities we offer children, the more intense will be their motivations and the richer their experiences. We must widen the range of topics and goals, the types of situations we offer and their degree of structure, the kinds and combinations of resources and materials, and the possible interactions with things, peers, and adults.”
—Loris Malaguzzi (1920–1994)
“He’s one of those know-it-all types that, if you flatter the wig off him, he chatter like a goony bird at mating time.”
—Michael Blankfort. Lewis Milestone. Johnson (Reginald Gardner)
“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)