HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

What is difference between nondeterministic polynomial time and exponential time?

Submitted by: @import:stackexchange-cs··
0
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.