Editing Complexity class (section)

===Computational problems===
Intuitively, a [[computational problem]] is just a question that can be solved by an [[algorithm]]. For example, "is the [[natural number]] <math>n</math> [[prime number|prime]]?" is a computational problem. A computational problem is mathematically represented as the [[set (mathematics)|set]] of answers to the problem. In the primality example, the problem (call it <math>\texttt{PRIME}</math>) is represented by the set of all natural numbers that are prime: <math>\texttt{PRIME} = \{ n \in \mathbb{N} | n \text{ is prime}\}</math>. In the theory of computation, these answers are represented as [[string (computer science)|strings]]; for example, in the primality example the natural numbers could be represented as strings of [[bit]]s that represent [[binary number]]s. For this reason, computational problems are often synonymously referred to as languages, since strings of bits represent [[formal language]]s (a concept borrowed from [[linguistics]]); for example, saying that the <math>\texttt{PRIME}</math> problem is in the complexity class '''[[P (complexity)|P]]''' is equivalent to saying that the language <math>\texttt{PRIME}</math> is in '''P'''.

====Decision problems====
[[Image:Decision Problem.svg|thumb|A [[decision problem]] has only two possible outputs, ''yes'' or ''no'' (alternatively, 1 or 0) on any input.]]
The most commonly analyzed problems in theoretical computer science are [[decision problem]]s—the kinds of problems that can be posed as [[yes–no question]]s. The primality example above, for instance, is an example of a decision problem as it can be represented by the yes–no question "is the [[natural number]] <math>n</math> [[prime number|prime]]". In terms of the theory of computation, a decision problem is represented as the set of input strings that a computer running a correct [[algorithm]] would answer "yes" to. In the primality example, <math>\texttt{PRIME}</math> is the set of strings representing natural numbers that, when input into a computer running an algorithm that correctly [[primality testing|tests for primality]], the algorithm answers "yes, this number is prime". This "yes-no" format is often equivalently stated as "accept-reject"; that is, an algorithm "accepts" an input string if the answer to the decision problem is "yes" and "rejects" if the answer is "no".

While some problems cannot easily be expressed as decision problems, they nonetheless encompass a broad range of computational problems.{{sfn|Arora|Barak|2009|p=28}} Other types of problems that certain complexity classes are defined in terms of include:

* [[Function problem]]s (e.g. '''[[FP (complexity)|FP]]''')
* [[counting problem (complexity)|Counting problem]]s (e.g. '''[[Sharp-P|#P]]''')
* [[Optimization problem]]s
* [[Promise problem]]s (see section "Other types of problems")