6
$\begingroup$

According to this video, EXP has problems that are exponentially difficult to check.

But according to this video, EXP are problems that are exponentially difficult to solve.

It would make sense to me, that if EXP contains problems that are exponentially difficult to check, that they would contain problems that are harder than NP-complete ones.

However, if it's true that EXP is problems that are just solvable in exponential time, why wouldn't they be equal? Wouldn't EXP therefore be a subset of NP (and so would R), as problems that are harder (like R) are still solvable in "non-deterministic" time? Because the term "non-deterministic" extends to any finite amount of time, correct?

Thank you in advance for resolving my confusion. If you could explain it as simply as possible, I would appreciate it, as I get easily bogged down by the set theory.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

A language $L$ belongs to $\mathsf{EXPTIME}$ if there is an algorithm deciding it which runs in time $O(2^{n^k})$ for some $k$.

A language $L$ belongs to $\mathsf{NEXPTIME}$ if there is an algorithm verifying it which runs in time $O(2^{n^k})$ for some $k$. In other words, a language $L$ belongs to $\mathsf{NEXPTIME}$ if there is a constant $k$ and a machine $M$ running in time $O(2^{n^k})$ such that $x \in L$ iff there exists $y$ of size at most $O(2^{|x|^k})$ such that $M(x,y) = 1$. Alternatively, a language $L$ belongs to $\mathsf{NEXPTIME}$ if it can be decided in nondeterministic time $O(2^{n^k})$ for some $k$.

You observe correctly that every problem in $\mathsf{NP}$ has an $\mathsf{EXPTIME}$ algorithm, that just goes over all possible witnesses. This shows that $\mathsf{NP} \subseteq \mathsf{EXPTIME}$. It is conjectured that the two classes are distinct. In contrast, it is believed that $\mathsf{EXPTIME} \neq \mathsf{NEXPTIME}$, and this is stronger than (i.e., implies) the more famous conjecture $\mathsf{P} \neq \mathsf{NP}$, through a padding argument.

Note that nondeterministic computation can still be time-bounded. For example, $\mathsf{NP}$ is the class of languages computed by nondeterministic polytime algorithms. The nondeterministic time hierarchy theorem shows that $\mathsf{NP} \neq \mathsf{NEXPTIME}$; similarly, the deterministic time hierarchy theorem shows that $\mathsf{P} \neq \mathsf{EXPTIME}$.

Improve this answer
$\endgroup$
9
  • $\begingroup$ This is helpful, thank you. So why is it conjectured that the two are distinct? Are there EXPTIME problems not in NP? This would be the only way that I could see 𝖭𝖯 ⊂ 𝖤𝖷𝖯𝖳𝖨𝖬𝖤 $\endgroup$
    – rb612
    Commented May 29, 2016 at 21:04
  • 2
    $\begingroup$ If we knew of EXPTIME problems which are not in NP, then it would have proved that the two classes are different. It is conjectured, however, that EXPTIME-complete problems are not in NP (this is equivalent to the two classes being different). The source for this conjecture is that unless there is reason to believe that two classes are equal, we believe that they are different. We could be wrong. $\endgroup$
    – Yuval Filmus
    Commented May 29, 2016 at 23:13
  • $\begingroup$ Thanks Yuval. That helps clear things up. But I'm still stuck on the second part of my original question. Here's where I'm still confused: you have a non-deterministic turing machine that has R time to solve a given problem. This means everything in R and EXP would fall under NP, unless EXP-complete problems and harder cannot be checked using a non-deterministic turing machine in a polynomial amount of time. So I don't understand how it's not the other way around, that the conjecture is 𝖤𝖷𝖯𝖳𝖨𝖬𝖤 ∪ R ⊆ NP $\endgroup$
    – rb612
    Commented May 30, 2016 at 1:34
  • $\begingroup$ Except now I just read that NEXP-complete problems cannot be verified in polynomial time. So I'm a bit confused to why EXP is verifiable in polynomial time but NEXP is not. $\endgroup$
    – rb612
    Commented May 30, 2016 at 1:48
  • 1
    $\begingroup$ Oh, it finally clicked! Sorry. Because we don't know of EXPTIME problems that aren't in NP, we don't know if all EXPTIME problems can be checked in polynomial time, and we conjecture that EXP-complete problems CANNOT be checked in polynomial time. Do I have it right? $\endgroup$
    – rb612
    Commented May 31, 2016 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.