# 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. Commented Dec 7, 2017 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)? Commented Dec 7, 2017 at 10:09
• Both of your functions are $O(e^{n^2})$, so they fall into exponential time. Commented Dec 7, 2017 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}$.

Nope. You are not right. As, a deterministic polynomial is a non-deterministic polynomial too. Hence, a non-deterministic polynomial class is not equivalent to exponential class.

To understand it better, you can think about the related Turing machine.

• I think this is still ok though since the exponential class contains everything solvable in exponential time or better. So problems solvable by deterministic polynomial time turing machines would still be in this class. The set of polynomial time solvable problems is a strict subset of the set of exponential time solvable problems I think. Commented Mar 29, 2021 at 10:06