Computational Problem - Types of Computational Problems

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

f_R(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.