Computational problem

Computational problem

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

"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 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.)

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), (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 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.


Promise problems

In computational complexity theory, 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 problems.

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 LyesLno. 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.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • 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. In this context, a… …   Wikipedia

  • Computational — may refer to: Computer Computational algebra Computational Aeroacoustics Computational and Information Systems Laboratory Computational and Systems Neuroscience Computational archaeology Computational auditory scene analysis Computational biology …   Wikipedia

  • Computational resource — In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems. The simplest computational resources are computation time, the number of steps necessary to… …   Wikipedia

  • Computational theory of mind — In philosophy, the computational theory of mind is the view that the human mind is an information processing system and that thinking is a form of computing. The theory was proposed in its modern form by Hilary Putnam in 1961[citation needed] and …   Wikipedia

  • Computational Diffie–Hellman assumption — The computational Diffie–Hellman (CDH assumption) is the assumption that a certain computational problem within a cyclic group is hard. Consider a cyclic group G of order q. The CDH assumption states that, given for a randomly chosen… …   Wikipedia

  • Computational Diffie-Hellman assumption — The computational Diffie Hellman (CDH) assumption is the assumption that a certain computational problem within a cyclic group is hard.Consider a cyclic group {mathbb G} of order q. The CDH assumption states that, given :(g,g^a,g^b) for a… …   Wikipedia

  • Computational geometry — is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to… …   Wikipedia

  • Computational creativity — (also known as artificial creativity, mechanical creativity or creative computation) is a multidisciplinary endeavour that is located at the intersection of the fields of artificial intelligence, cognitive psychology, philosophy, and the arts.… …   Wikipedia

  • Computational electromagnetics — Computational electromagnetics, computational electrodynamics or electromagnetic modeling is the process of modeling the interaction of electromagnetic fields with physical objects and the environment. It typically involves using computationally… …   Wikipedia

  • Computational thinking — is a new problem solving method, named for its extensive use of computer science techniques. The term computational thinking was first used by Seymour Papert in 1996.[1] Computational thinking can be used to algorithmically solve complicated… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”