# What is difference between nondeterministic polynomial time and exponential time?

I am not very into computer science theory but i feel like people are defining nondeterministic polynomial time as if it is another name of exponential time. I would be happy if you clarify it. thank you

• Who are those people defining them so they could be confused? I'd be surprised to see such a definition since normal definitions of nondeterministic polynomial time don't mention exponential functions and definitions of exponential time obviously do. – Alexey Romanov Dec 7 '17 at 7:45

Every nondeterministic polynomial time algorithm can be converted to an exponential time algorithm, where exponential means $O(e^{n^C})$ for some constant $C$. The converse probably doesn't hold.
• Aren't $O(n!)$ and $O(n^n)$ also exponential times or do they have their own name (perhaps meta-exponential)? – clemens Dec 7 '17 at 10:09
• Both of your functions are $O(e^{n^2})$, so they fall into exponential time. – Yuval Filmus Dec 7 '17 at 11:20
The class of problems solvable by a nondeterministic Turing Machine in polynomial time is $\mathsf{NP}$, for Nondeterministic polynomial time. This definition has nothing to do with exponential time or exponential functions at all. The class of problems solvable by a deterministic Turing Machine in exponential time is $\mathsf{EXP}$.
However, can consider the computation tree for a nondeterministic polynomial time TM. If we perform breadth-first search on this tree, we can simulate all possible computational branches in deterministic exponential time. This shows that $\mathsf{NP}\subseteq\mathsf{EXP}$, though it certainly isn't necessarily the case that $\mathsf{NP} = \mathsf{EXP}$.