6
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ Maybe you should have done more reading? Looking at the complexity zoo, you see quickly that there are many classes "above" NP, and many of those are proper supersets. There are also meta results that state that there are arbitrarily hard problems; any introduction to complexity introduces one of these (or should). $\endgroup$ – Raphael Jul 4 '17 at 18:00
  • 1
    $\begingroup$ "Please explain clearly why it takes exponential time" -- (interesting) lower bounds are hard to come by. Which means that the proofs are often tough, and even so they are frequently not very insightful. If we knew what makes problems hard, we'd probably be closer to solving the P?=NP question. $\endgroup$ – Raphael Jul 4 '17 at 18:02
  • 3
    $\begingroup$ Note also that "takes at most polynomial time" and "takes at least exponential time" are not antonyms. There's stuff in between. Some NP-hard problems even have sub-exponential algorithms (depending on the definition of "sub-exponential")! $\endgroup$ – Raphael Jul 4 '17 at 18:05
  • $\begingroup$ non-deterministically exponential time? Ok, computing 1 + 1 will non-deterministically be affected by cosmic rays, alpha particles and quantum fluctuations in the transistors which will, during some execution, by chance take exponential time $\endgroup$ – cat Jul 5 '17 at 0:47
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Would you mind explaining how the winning strategy between two people is NEXP? I understand for every single choice of the first person we need to see all moves by the second person. I am getting confused that how it leads to exponential time? $\endgroup$ – ViX28 Jul 4 '17 at 19:15
  • $\begingroup$ @ViX28, if number of possible configurations is hyperexponential of the size of the field, it may take non-deterministically at least exponential time to solve it. Not for all problems, of course (unless $\mathsf{EXP = NEXP}$). $\endgroup$ – rus9384 Jul 4 '17 at 20:59
  • 1
    $\begingroup$ @ViX28 Different games have different complexities, depending on the rules of the game. For example, games that involve placing pieces on a board but never moving or removing them (e.g., tic-tac-toe and connect 4) can typically be solved in $\mathrm{PSPACE}$ but games where pieces can move around can potentially have very long plays. For example, in chess the fact that I probably have about 30 moves available, to each of which you have about 30 replies, to each of which I have about 30 replies and so on naturally leads to exponential complexity. $\endgroup$ – David Richerby Jul 4 '17 at 21:49
  • $\begingroup$ Actually, Wikipedia's list of complexities of well-known games doesn't include anything that's $\mathrm{NEXP}$-complete, so I've removed that claim from my answer. One could certainly invent $\mathrm{NEXP}$-complete games but that would be a pretty weak point. $\endgroup$ – David Richerby Jul 4 '17 at 21:50
5
$\begingroup$

According to the Nondeterministic time hierarchy theorem, $\mathsf{NEXP\neq NP}$, which means there are languages decidable in nondeterministic exponential time, but not with nondeterministic polynomial time. A simple consequence is that no $\mathsf{NEXP}$ complete problem can lie inside $\mathsf{NP}$, which means that the following language requires exponential nondeterministic time to solve:

$L=\left\{\left(n,\langle M\rangle,x\right) \big|\hspace{1mm} \exists w\in\{0,1\}^{\le n} : M(x,w)\right\}$

Note that if in the above you replace the binary representation of $n$ with its unary representation $1^n$ then the problem becomes $\mathsf{NP}$ complete rather then $\mathsf{EXP}$-complete. This is an example of a more general phenomena, where many $\mathsf{NP}$ complete problems can be turned into $\mathsf{EXP}$-complete problems by giving a succinct description of the inputs. More details about this and some examples of more natural $\mathsf{EXP}$-complete problems can be found in this question from cstheory.

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