Im studying Complexity Theory and i have a question.
What principle establishes that every NP problem can be solved by a deterministic turing machine in a exponential time ?
['https://cs.stackexchange.com/questions/88406', 'https://cs.stackexchange.com', 'https://cs.stackexchange.com/users/84677/']
Excellent question! Nondeterminism first appears (so it seems) in a classical paper of Rabin and Scott, [Finite automata and their decision problems](http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf), in which the authors first describe finite automata as a better abstract model for digital computers than Turing machines, and then define several extensions of the basic model, including nondeterministic finite automata. They seem to be completely unaware of what is bothering you. For them, nondeterminism is a way of reducing the number of states, and of simplifying the proofs of various closure properties.

Indeed, when simulating finite automata on an actual digital computer, NFAs can be simulated directly, by keeping track of the set of reachable states at any given point. This could be more efficient than converting the NFA to a DFA, especially if typically not many states are reachable.

Just as NFAs are equivalent to DFAs but are more state-efficient, so NTMs are equivalent to DTMs but are more time-efficient (here TM is short for *Turing machine*). However, in contrast to NFAs, there is no known way to efficiently simulate nondeterministic Turing machines on a digital computer (this is essentially the P vs NP question). Why then do we care about nondeterministic Turing machines?

There might be several reasons (for example, by analogy to complexity hierarchies in descriptive set theory and in recursion theory), but I think the most appealing one is the complexity class NP, whose natural definition is via nondeterministic Turing machines (there are other equivalent definitions using only deterministic Turing machines, which verify that an input belongs to the language using a polynomial length witness). It remains to convince you why NP is important.

Let's think of P as the set of (decision) problems which can be solved efficiently (there are various problems with this point of view, but let's ignore them). Some problems seem to be beyond P, for example [SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) (here we encounter another problem which we ignore: SAT seems to be solvable efficiently on practical influences). How can we tell that SAT is not in P? The best answer we have found for this question is this:

> 
> SAT is in P if and only if Maximum Clique is in P if and only if Minimum Vertex Cover is in P if and only if ...
> 
> 
> 

Individually, each of these problems seems hard, and this multitude makes the case more convincing for their inherent difficulty. It's enough to accept that one of SAT, Maximum Clique, Minimum Vertex Cover is difficult, and then it follows that all the rest are also difficult.

Where do the problems SAT, Maximum Clique, Minimum Vertex Cover come from? They are *NP-complete* problems, intuitively the "hardest" problems in NP (with respect to polynomial time reductions). So what the class NP allows us to do is to isolate a large class of problems which seem difficult.

Now some problems, like the halting problem, are provably difficult; in fact, uncomputable. But these problems are *too difficult*: the halting problem is much harder than SAT, so the fact that the halting problem is difficult has no bearing on SAT. Problems in NP are on the one hand not insanely difficult, and on the other hand some of them do seem too hard to solve efficiently.

Indeed, NP is only the first rung in a ladder of difficulty known as the [polynomial hierarchy](https://en.wikipedia.org/wiki/Polynomial_hierarchy), which as mentioned before is inspired by other hierarchies such as the arithmetical hierarchy and the Borel hierarchy. In some sense, NP comes up naturally in this context, as the polynomially bounded version of the arithmetical hierarchy. (For another take, check out [descriptive complexity theory](https://en.wikipedia.org/wiki/Descriptive_complexity_theory).)

Finally, what about NPDAs? Why should we care about them? In a sense, we shouldn't, since in practice, most context-free languages we come in contact with (as grammars of programming languages) are deterministic context-free, and in fact belong to even more restricted subclasses. The importance of NPDAs lies in their equivalence with general context-free grammars: a language is context-free if and only if it is accepted by some NPDA. Since context-free grammars can be parsed efficiently, this also shows that NPDAs can be simulated efficiently by digital computers.
A complexity class is a set of problems (or languages) that can be solved on a given computational model with constraints on the use of resources (such as time and/or space for sequential computations). Therefore, it's pretty easy do define a complexity class. However, it's hard instead to define a *meaningful* complexity class, since the class

* must capture a genuine computational phenomenon;
* must contain natural and relevant problems;
* should be ideally characterized by natural
problems;
* should be robust under variations in model of computation;
* should be possibly closed under operations (such as complement etc).

Regarding nondeterminism and the class NP in particular, it captures an important computational feature of many problems: *exhaustive search* works. Note that this has nothing to do with efficiency in solving a problem: indeed, we will never solve a problem by using a brute force approach. The class also includes many natural, practical problems.

Besides the technical details (a non deterministic Turing Machine has a transition relation instead of a transition function, so that given the current configuration there can be several next configurations; moreover, for the nondeterministic Turing Machine there is an asymmetric accept/reject criterion), nondeterminism is usually explained, consistently with this perspective, in terms of an *oracle* that magically guesses a solution if one exists (it's like having a parallel computer spawning infinitely many processes, with each process in charge of verifying a possible solution).