4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Alexey Romanov Dec 7 '17 at 7:45
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Aren't $O(n!)$ and $O(n^n)$ also exponential times or do they have their own name (perhaps meta-exponential)? $\endgroup$ – clemens Dec 7 '17 at 10:09
  • 2
    $\begingroup$ Both of your functions are $O(e^{n^2})$, so they fall into exponential time. $\endgroup$ – Yuval Filmus Dec 7 '17 at 11:20
3
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.