Editing Complexity class (section)

==Background==
Complexity classes are [[Set (mathematics)|sets]] of related [[computational problem]]s. They are defined in terms of the computational difficulty of solving the problems contained within them with respect to particular computational resources like time or memory. More formally, the definition of a complexity class consists of three things: a type of computational problem, a model of computation, and a bounded computational resource. In particular, most complexity classes consist of [[decision problem]]s that can be solved by a [[Turing machine]] with bounded [[time complexity|time]] or [[space complexity|space]] resources. For example, the complexity class '''[[P (complexity)|P]]''' is defined as the set of [[decision problem]]s that can be solved by a [[deterministic Turing machine]] in [[polynomial time]].

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

===Computational models===
To make concrete the notion of a "computer", in theoretical computer science problems are analyzed in the context of a [[computational model]]. Computational models make exact the notions of computational resources like "time" and "memory". In [[computational complexity theory]], complexity classes deal with the ''inherent'' resource requirements of problems and not the resource requirements that depend upon how a physical computer is constructed. For example, in the real world different computers may require different amounts of time and memory to solve the same problem because of the way that they have been engineered. By providing an abstract mathematical representations of computers, computational models abstract away superfluous complexities of the real world (like differences in [[Processor (computing)|processor]] speed) that obstruct an understanding of fundamental principles.

The most commonly used computational model is the [[Turing machine]]. While other models exist and many complexity classes are defined in terms of them (see section [[Complexity class#Other models of computation|"Other models of computation"]]), the Turing machine is used to define most basic complexity classes. With the Turing machine, instead of using standard units of time like the second (which make it impossible to disentangle running time from the speed of physical hardware) and standard units of memory like [[byte]]s, the notion of time is abstracted as the number of elementary steps that a Turing machine takes to solve a problem and the notion of memory is abstracted as the number of cells that are used on the machine's tape. These are explained in greater detail below.

It is also possible to use the [[Blum axioms]] to define complexity classes without referring to a concrete [[computational model]], but this approach is less frequently used in complexity theory.

====Deterministic Turing machines====
{{Main|Turing machine}}
[[File:Turing machine 2b.svg|thumb|right|An illustration of a Turing machine. The "B" indicates the blank symbol.]]
A '''Turing machine''' is a mathematical model of a general computing machine. It is the most commonly used model in complexity theory, owing in large part to the fact that it is believed to be as powerful as any other model of computation and is easy to analyze mathematically. Importantly, it is believed that if there exists an algorithm that solves a particular problem then there also exists a Turing machine that solves that same problem (this is known as the [[Church–Turing thesis]]); this means that it is believed that ''every'' algorithm can be represented as a Turing machine.

Mechanically, a Turing machine (TM) manipulates symbols (generally restricted to the bits 0 and 1 to provide an intuitive connection to real-life computers) contained on an infinitely long strip of tape. The TM can read and write, one at a time, using a tape head. Operation is fully determined by a finite set of elementary instructions such as "in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6". The Turing machine starts with only the input string on its tape and blanks everywhere else. The TM accepts the input if it enters a designated accept state and rejects the input if it enters a reject state. The deterministic Turing machine (DTM) is the most basic type of Turing machine. It uses a fixed set of rules to determine its future actions (which is why it is called "[[deterministic]]").

A computational problem can then be defined in terms of a Turing machine as the set of input strings that a particular Turing machine accepts. For example, the primality problem <math>\texttt{PRIME}</math> from above is the set of strings (representing natural numbers) that a Turing machine running an algorithm that correctly [[primality test|tests for primality]] accepts. A Turing machine is said to '''recognize''' a language (recall that "problem" and "language" are largely synonymous in computability and complexity theory) if it accepts all inputs that are in the language and is said to '''decide''' a language if it additionally rejects all inputs that are not in the language (certain inputs may cause a Turing machine to run forever, so [[Recursive set|decidability]] places the additional constraint over [[Recursively enumerable set|recognizability]] that the Turing machine must halt on all inputs). A Turing machine that "solves" a problem is generally meant to mean one that decides the language.

Turing machines enable intuitive notions of "time" and "space". The [[time complexity]] of a TM on a particular input is the number of elementary steps that the Turing machine takes to reach either an accept or reject state. The [[space complexity]] is the number of cells on its tape that it uses to reach either an accept or reject state.

====Nondeterministic Turing machines====
{{Main|Nondeterministic Turing machine}}
[[Image:Difference_between_deterministic_and_Nondeterministic.svg|thumb|350px|right| A comparison of deterministic and nondeterministic computation. If any branch on the nondeterministic computation accepts then the NTM accepts.]]

The deterministic Turing machine (DTM) is a variant of the nondeterministic Turing machine (NTM). Intuitively, an NTM is just a regular Turing machine that has the added capability of being able to explore multiple possible future actions from a given state, and "choosing" a branch that accepts (if any accept). That is, while a DTM must follow only one branch of computation, an NTM can be imagined as a computation tree, branching into many possible computational pathways at each step (see image). If at least one branch of the tree halts with an "accept" condition, then the NTM accepts the input. In this way, an NTM can be thought of as simultaneously exploring all computational possibilities in parallel and selecting an accepting branch.{{sfn|Sipser|2006|p=48, 150}} NTMs are not meant to be physically realizable models, they are simply theoretically interesting abstract machines that give rise to a number of interesting complexity classes (which often do have physically realizable equivalent definitions). 

The [[time complexity]] of an NTM is the maximum number of steps that the NTM uses on ''any'' branch of its computation.{{sfn|Sipser|2006|p=255}} Similarly, the [[space complexity]] of an NTM is the maximum number of cells that the NTM uses on any branch of its computation.

DTMs can be viewed as a special case of NTMs that do not make use of the power of nondeterminism. Hence, every computation that can be carried out by a DTM can also be carried out by an equivalent NTM. It is also possible to simulate any NTM using a DTM (the DTM will simply compute every possible computational branch one-by-one). Hence, the two are equivalent in terms of computability. However, simulating an NTM with a DTM often requires greater time and/or memory resources; as will be seen, how significant this slowdown is for certain classes of computational problems is an important question in computational complexity theory.

===Resource bounds===
Complexity classes group computational problems by their resource requirements. To do this, computational problems are differentiated by [[upper bound]]s on the maximum amount of resources that the most efficient algorithm takes to solve them. More specifically, complexity classes are concerned with the ''rate of growth'' in the resources required to solve particular computational problems as the input size increases. For example, the amount of time it takes to solve problems in the complexity class '''[[P (complexity)|P]]''' grows at a [[polynomial]] rate as the input size increases, which is comparatively slow compared to problems in the exponential complexity class '''[[EXPTIME]]''' (or more accurately, for problems in '''EXPTIME''' that are outside of '''P''', since <math>\mathsf{P}\subseteq\mathsf{EXPTIME}</math>).

Note that the study of complexity classes is intended primarily to understand the ''inherent'' complexity required to solve computational problems. Complexity theorists are thus generally concerned with finding the smallest complexity class that a problem falls into and are therefore concerned with identifying which class a computational problem falls into using the ''most efficient'' algorithm. There may be an algorithm, for instance, that solves a particular problem in exponential time, but if the most efficient algorithm for solving this problem runs in polynomial time then the inherent time complexity of that problem is better described as polynomial.

====Time bounds====
{{Main|Time complexity}}
The [[time complexity]] of an algorithm with respect to the Turing machine model is the number of steps it takes for a Turing machine to run an algorithm on a given input size. Formally, the time complexity for an algorithm implemented with a Turing machine <math>M</math> is defined as the function <math>t_M: \mathbb{N} \to \mathbb{N}</math>, where <math>t_M(n)</math> is the maximum number of steps that <math>M</math> takes on any input of length <math>n</math>.

In computational complexity theory, theoretical computer scientists are concerned less with particular runtime values and more with the general class of functions that the time complexity function falls into. For instance, is the time complexity function a [[polynomial]]? A [[logarithmic function]]? An [[exponential function]]? Or another kind of function? 

====Space bounds====
{{Main|Space complexity}}
The [[space complexity]] of an algorithm with respect to the Turing machine model is the number of cells on the Turing machine's tape that are required to run an algorithm on a given input size. Formally, the space complexity of an algorithm implemented with a Turing machine <math>M</math> is defined as the function <math>s_M: \mathbb{N} \to \mathbb{N}</math>, where <math>s_M(n)</math> is the maximum number of cells that <math>M</math> uses on any input of length <math>n</math>.