Cheap and Secure Web Hosting Provider : See Now

[Solved]: Is EXPTIME "solvable" or "checkable" in exponential time?

, , No Comments
Problem Detail: 

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.

Asked By : rb612

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/58009

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback