snippetModerate
Give one example where it takes Non- deterministically exponential time to solve the problem?
Viewed 0 times
problemthenonexamplewhereexponentialgivetimeonesolve
Problem
I am a starter in complexity theory though I have fair knowledge in Turing machine. I know what it means to be non-deterministically polynomial time solvable but I am trying to understand where the time goes beyond polynomial time even using non-deterministic concept. Is it possible or we can do everything in polynomial time using non-deterministic concept though in reality it can not be implemented. Therefore, I am looking for an example where we can't do it in polynomial time rather it takes exponential time even after using non-deterministic concept. Please explain clearly why it takes exponential time(non-deterministically).
Solution
There are problems that cannot be solved in polynomial time on a nondeterministic machine. Indeed, there are problems that cannot be solved on any Turing machine, such as the halting problem.
We know from the nondeterministic version of the time hierarchy theorem that there are things that can be done in exponential time on a nondeterministic TM that cannot be done in polynomial time. That is, $\mathrm{NP}\subsetneq\mathrm{NEXP}$.
Wikipedia gives several examples of $\mathrm{NEXP}$-complete problems: these are examples of problems that are provably not in $\mathrm{NP}$.
We know from the nondeterministic version of the time hierarchy theorem that there are things that can be done in exponential time on a nondeterministic TM that cannot be done in polynomial time. That is, $\mathrm{NP}\subsetneq\mathrm{NEXP}$.
Wikipedia gives several examples of $\mathrm{NEXP}$-complete problems: these are examples of problems that are provably not in $\mathrm{NP}$.
Context
StackExchange Computer Science Q#77547, answer score: 10
Revisions (0)
No revisions yet.