1.
Computational complexity theory
–
A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying the amount of resources needed to solve them, such as time and storage. Other complexity measures are used, such as the amount of communication, the number of gates in a circuit. One of the roles of computational complexity theory is to determine the limits on what computers can. Closely related fields in computer science are analysis of algorithms. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources, a computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a problem is referred to as a problem instance. In computational complexity theory, a problem refers to the question to be solved. In contrast, an instance of this problem is a rather concrete utterance, for example, consider the problem of primality testing. The instance is a number and the solution is yes if the number is prime, stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input. For this reason, complexity theory addresses computational problems and not particular problem instances, when considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet, as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices and this can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the objects of study in computational complexity theory. A decision problem is a type of computational problem whose answer is either yes or no. A decision problem can be viewed as a language, where the members of the language are instances whose output is yes. The objective is to decide, with the aid of an algorithm, if the algorithm deciding this problem returns the answer yes, the algorithm is said to accept the input string, otherwise it is said to reject the input. An example of a problem is the following

2.
Polynomial hierarchy
–
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. It is a counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. There are multiple equivalent definitions of the classes of the polynomial hierarchy. If any Σ k P = Σ k +1 P, or if any Σ k P = Π k P, then the hierarchy collapses to level k, in particular, if P = NP, then the hierarchy collapses completely. The union of all classes in the hierarchy is the complexity class PH. The polynomial hierarchy is an analogue of the hierarchy and arithmetical hierarchy. It is known that PH is contained within PSPACE, but it is not known whether the two classes are equal. One useful reformulation of this problem is that PH = PSPACE if, if the polynomial hierarchy has any complete problems, then it has only finitely many distinct levels. Since there are PSPACE-complete problems, we know that if PSPACE = PH, then the hierarchy must collapse. Each class in the hierarchy contains ≤ m P -complete problems. Furthermore, each class in the hierarchy is closed under ≤ m P -reductions, meaning that for a class C in the hierarchy. These two facts together imply that if K i is a problem for Σ i P, then Σ i +1 P = N P K i. For instance, Σ2 P = N P S A T, in other words, if a language is defined based on some oracle in C, then we can assume that it is defined based on a complete problem for C. Complete problems therefore act as representatives of the class for which they are complete, the Sipser–Lautemann theorem states that the class BPP is contained in the second level of the polynomial hierarchy. Kannans theorem states that for any k, Σ2 is not contained in SIZE, todas theorem states that the polynomial hierarchy is contained in P#P. EXPTIME Exponential hierarchy Arithmetic hierarchy A. R. Meyer and L. J. Stockmeyer. The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space, in Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pp. 125–129,1972. The paper that introduced the polynomial hierarchy, theoretical Computer Science, vol.3, pp. 1–22,1976. Michael R. Garey and David S. Johnson, computers and Intractability, A Guide to the Theory of NP-Completeness

3.
Non-deterministic Turing machine
–
In theoretical computer science, a Turing machine is a theoretical machine that is used in thought experiments to examine the abilities and limitations of computers. In essence, a Turing machine is imagined to be a computer that reads. It determines what action it should perform next according to its internal state, an example of one of a Turing Machines rules might thus be, If you are in state 2 and you see an A, change it to B and move left. In a deterministic Turing machine, the set of rules prescribes at most one action to be performed for any given situation, by contrast, a non-deterministic Turing machine may have a set of rules that prescribes more than one action for a given situation. For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the one position to the right. For example, an X on the tape in state 3 might allow the NTM to write a Y, move right, and switch to state 5, or to write an X, move left, and stay in state 3. L is the movement to the left, and R is to the right, the difference with a standard Turing machine is that for those, the transition relation is a function. How does the NTM know which of these actions it should take, there are two ways of looking at it. One is to say that the machine is the luckiest possible guesser, it always picks a transition that eventually leads to an accepting state, the other is to imagine that the machine branches into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single computation path that it follows, If at least one branch of the tree halts with an accept condition, we say that the NTM accepts the input. NTMs can compute the results as DTMs, that is, they are capable of computing the same values. The time complexity of these varies, however, as is discusssed below. NTMs effectively include DTMs as special cases, so it is clear that DTMs are not more powerful. The 3-tape DTMs are easily simulated with a normal single-tape DTM, therefore, the length of an accepting computation of the DTM is, in general, exponential in the length of the shortest accepting computation of the NTM. This is considered to be a property of simulations of NTMs by DTMs, the most famous unresolved question in computer science. The time complexity of NTMs is not the same as for DTMs and it is a common misconception that quantum computers are NTMs. It is believed but has not been proven that the power of computers is incomparable to that of NTMs. That is, problems likely exist that an NTM could efficiently solve that a computer cannot