1
$\begingroup$

I have a question about this. Because if the input binary strings have size of O(n), it takes exponential time to list all possibilities of it. If an language is in NEXP, then we can list all input possible input strings and then use exponential time to check each one, which is still in exponential time in total. It seems like NEXP=EXP under this circumstance.

$\endgroup$
1
  • $\begingroup$ What does $n$ denote? $\endgroup$ – Dmitri Urbanowicz Oct 2 '18 at 7:52
1
$\begingroup$

"When the input has size $O(n)$." Unless otherwise stated, $n$ is defined to be the length of the input. So, generally speaking, the input length is just $n$, and your question is just

Is EXP equal to NEXP?

We don't know, but we suspect not. Nondeterminism seems to add extra power that we don't know how to simulate deterministically without requiring exponential time.

If an language is in NEXP, then we can list all input possible input strings and then use exponential time to check each one

That doesn't make sense. In a computational decision problem, you are given an input and you must determine whether the answer is "yes" or "no" for that specific input. Enumerating other possible inputs doesn't seem helpful: if you're asked a question, your job is to answer that question, not list off all the other questions you could have been asked instead.

$\endgroup$
4
  • $\begingroup$ Let's say given an input n, problem A can be verified in exponential time. Isn't it true that problem A can also be decided in exponential time by running the NDTM 2^n times? $\endgroup$ – Yiyou Chen Oct 2 '18 at 17:33
  • $\begingroup$ Because each run of the Turing machine is exponentially long, and therefore may make exponetially many nondeterministic choices. That means there could be $2^{2^n}$ different runs that you need to simulate. $\endgroup$ – David Richerby Oct 2 '18 at 17:42
  • $\begingroup$ Does it mean that the NDTM used to verify one input n1 might be different from the one that can be used to verify another input n2? $\endgroup$ – Yiyou Chen Oct 2 '18 at 19:01
  • $\begingroup$ No, there is only one nondeterministic machine. I think your underlying problem here is that you're confused by nondeterminism. Wikipedia has a good introduction, as should any textbook on the theory of computation. $\endgroup$ – David Richerby Oct 2 '18 at 19:48
0
$\begingroup$

A language $L$ is in NEXP if there is a polynomial $p(n)$ and a Turing machine $T$ running in time $2^{p(n)}$ (where $n$ is the input length, in bits) such that:

  • If $x \in L$ then there exists a string $y$, of length at most $2^{p(|x|)}$, such that $T(x,y)$ returns Yes.

  • If $x \notin L$ then for all strings $y$ of length at most $2^{p(|x|)}$ it holds that $T(x,y)$ returns No.

The string $y$ can be exponentially longer than $x$, and so brute-forcing $y$ would require double exponential time.

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