gotchaMinor
What is difference between nondeterministic polynomial time and exponential time?
Viewed 0 times
whatpolynomialexponentialtimedifferencebetweennondeterministicand
Problem
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
Solution
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.
Context
StackExchange Computer Science Q#85030, answer score: 6
Revisions (0)
No revisions yet.