This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(October 2015) (Learn how and when to remove this message)

Intheoretical computer science, a problem is one that asks for a solution in terms of analgorithm. For example, the problem offactoring

"Given a positive integern, find a nontrivial prime factor ofn."

is a computational problem that has a solution, as there are many knowninteger factorization algorithms. A computational problem can be viewed as aset ofinstances orcases together with a, possibly empty, set ofsolutions for every instance/case. The question then is, whether there exists an algorithm that maps instances to solutions. For example, in thefactoring problem, the instances are the integersn, and solutions are prime numbersp that are the nontrivial prime factors ofn. An example of a computational problem without a solution is theHalting problem. Computational problems are one of the main objects of study in theoretical computer science.

One is often interested not only in mere existence of an algorithm, but also how efficient the algorithm can be. The field ofcomputational complexity theory addresses such questions by determining the amount of resources (computational complexity) solving a given problem will require, and explain why some problems areintractable orundecidable. Solvable computational problems belong tocomplexity classes that define broadly the resources (e.g. time, space/memory, energy, circuit depth) it takes to compute (solve) them with variousabstract machines. For example, the complexity classes

• P, problems that consume polynomial time for deterministic classical machines
• BPP, problems that consume polynomial time for probabilistic classical machines (e.g. computers with random number generators)
• BQP, problems that consume polynomial time for probabilistic quantum machines.

Both instances and solutions are represented by binarystrings, namely elements of {0, 1}^*.^[a] For example,natural numbers are usually represented as binary strings usingbinary encoding. This is important since the complexity is expressed as a function of the length of the input representation.

Adecision problem is a computational problem where the answer for every instance is either yes or no. An example of a decision problem isprimality testing:

"Given a positive integern, determine ifn is prime."

A decision problem is typically represented as the set of all instances for which the answer isyes. For example, primality testing can be represented as the infinite set

L = {2, 3, 5, 7, 11, ...}

In asearch 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 arelation consisting of all the instance-solution pairs, called asearch relation. For example, factoring 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), wherep is a prime factor ofn.

Acounting problem asks for the number of solutions to a given search problem. For example, a counting problem associated with factoring is

"Given a positive integern, count the number of nontrivial prime factors ofn."

A counting problem can be represented by a functionf from {0, 1}^* to the nonnegative integers. For a search relationR, the counting problem associated toR is the function

f_R(x) = |{y:R(x,y) }|.

Anoptimization problem asks for finding a "best possible" solution among the set of all possible solutions to a search problem. One example is themaximum independent set problem:

"Given a graphG, find an independent set ofG of maximum size."

Optimization problems are represented by their objective function and their constraints.

In afunction problem a single output (of atotal function) is expected for every input, but the output is more complex than that of adecision problem, that is, it isn't just "yes" or "no". One of the most famous examples is the traveling salesman problem:

"Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city."

It is anNP-hard problem incombinatorial optimization, important inoperations research andtheoretical computer science.

Incomputational 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 calledpromise problems.

The following is an example of a (decision) promise problem:

"Given a graphG, determine if everyindependent set inG has size at most 5, orG 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 (L_yes,L_no) of {0, 1}^*. The valid instances are those inL_yes ∪L_no.L_yes andL_no represent the instances whose answer isyes andno, respectively.

Promise problems play an important role in several areas ofcomputational complexity, includinghardness of approximation,property testing, andinteractive proof systems.

• Lateral computing, alternative approaches to solving problems computationally
• Model of computation
• Transcomputational problem

• Even, Shimon;Selman, Alan L.; Yacobi, Yacov (1984), "The complexity of promise problems with applications to public-key cryptography",Information and Control,61 (2):159–173,doi:10.1016/S0019-9958(84)80056-X.
• Goldreich, Oded (2008),Computational Complexity: A Conceptual Perspective,Cambridge University Press,ISBN 978-0-521-88473-0.
• Goldreich, Oded;Wigderson, Avi (2008), "IV.20 Computational Complexity", inGowers, Timothy; Barrow-Green, June;Leader, Imre (eds.),The Princeton Companion to Mathematics, Princeton University Press, pp. 575–604,ISBN 978-0-691-11880-2.

• Computational problems
• Theoretical computer science

• Articles lacking in-text citations from October 2015
• All articles lacking in-text citations
• Articles with short description
• Short description is different from Wikidata