Complexity class
In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems and using other models of computation.
The study of the relationships between complexity classes is a major area of research in theoretical computer science. There are often general hierarchies of complexity classes; for example, it is known that a number of fundamental time and space complexity classes relate to each other in the following way:
L⊆'NL⊆P'⊆NP⊆PSPACE⊆EXPTIME⊆NEXPTIME⊆'EXPSPACE
Where ⊆ denotes the subset relation. However, many relationships are not yet known; for example, one of the most famous open problems in computer science concerns whether P' equals NP. The relationships between classes often answer questions about the fundamental nature of computation. The P versus NP problem, for instance, is directly related to questions of whether nondeterminism adds any computational power to computers and whether problems having solutions that can be quickly checked for correctness can also be quickly solved.
Background
Complexity classes are sets of related computational problems. 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 problems that can be solved by a Turing machine with bounded time or space resources. For example, the complexity class P is defined as the set of decision problems 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 prime?" is a computational problem. A computational problem is mathematically represented as the set of answers to the problem. In the primality example, the problem is represented by the set of all natural numbers that are prime:. In the theory of computation, these answers are represented as strings; for example, in the primality example the natural numbers could be represented as strings of bits that represent binary numbers. For this reason, computational problems are often synonymously referred to as languages, since strings of bits represent formal languages ; for example, saying that the problem is in the complexity class P is equivalent to saying that the language is in P.Decision problems
The most commonly analyzed problems in theoretical computer science are decision problems—the kinds of problems that can be posed as yes–no questions. 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 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, is the set of strings representing natural numbers that, when input into a computer running an algorithm that correctly 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. Other types of problems that certain complexity classes are defined in terms of include:
- Function problems
- Counting problems
- Optimization problems
- Promise problems
Computational models
The most commonly used computational model is the Turing machine. While other models exist and many complexity classes are defined in terms of them, 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 and standard units of memory like bytes, 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
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 means that it is believed that every algorithm can be represented as a Turing machine.Mechanically, a Turing machine manipulates symbols 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 is the most basic type of Turing machine. It uses a fixed set of rules to determine its future actions.
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 from above is the set of strings that a Turing machine running an algorithm that correctly tests for primality accepts. A Turing machine is said to recognize a language 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. 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
The deterministic Turing machine is a variant of the nondeterministic Turing machine. 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. 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. 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. 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.The time complexity of an NTM is the maximum number of steps that the NTM uses on any branch of its computation. 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. 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.