6
$\begingroup$

We know that $NP\subseteq EXP$ but not whether it is strict.

The Exponential Time Hypothesis (ETH) states that SAT cannot be solved in subexponential time. My understanding is that most computer scientists believe that ETH is true.

  • It seems to me that ETH is equivalent to saying NP=EXP, but this is not so. What is the essential difference between the two?

  • Do most computer scientists believe that NP=EXP and that ETH is true? If not, why?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

No, ETH is not equivalent to saying $\mathit{NP} = \mathit{EXPTIME}$.

While ETH is consistent with the fact that $\mathit{NP} \subseteq \mathit{EXPTIME}$, it does not imply equivalence.

As far as $\mathit{SAT}$ goes, we know that $\mathit{SAT}$ can be decided in time $O(2^n)$, so $\mathit{SAT} \in \mathit{EXPTIME}$. (This is independent of whether ETH holds or not).

ETH on the other hand gives only lower bounds on how fast can $\mathit{SAT}$ be decided. I.e., there are no algorithms with runtime, for example, $O(2^{({\log n})^2})$. This run time is not polynomial, but sub-exponential.

  1. It is possible that $\mathit{P} = \mathit{NP} \neq \mathit{EXPTIME}$. The first equality implies that ETH is false, as this means $\mathit{SAT}$ has a poly-time algorithm.

  2. It is possible that $\mathit{P} \neq \mathit{NP}$ and $\mathit{NP} \neq \mathit{EXPTIME}$, but ETH is true. I think this is what most people believe, but neither of the two inequalities nor ETH is proved.

  3. It is possible that $\mathit{P} \neq \mathit{NP}$ and $\mathit{NP} \neq \mathit{EXPTIME}$, but ETH is false, for example, if $\mathit{SAT}$ can be decided in $O(2^{({\log n})^2})$ time.

  4. It is also possible that $\mathit{P} \neq \mathit{NP} = \mathit{EXPTIME}$. But the last equality implies that ETH is true. This is because there are problems in $EXPTIME$ whose algorithms have an exponential lower bound. If they can be converted to $\mathit{SAT}$ in poly-time, then $\mathit{SAT}$ must also have an exponential lower-bound, which is basically ETH.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "This is because there are problems in 𝐸𝑋𝑃𝑇𝐼𝑀𝐸 whose algorithms have an exponential lower-bound". How is this proven? $\endgroup$
    – user56834
    Commented Jun 16 at 4:21
  • 1
    $\begingroup$ @user56834 By time hierarchy theorem. $\endgroup$
    – Maja Piechotka
    Commented Jun 16 at 15:40
5
$\begingroup$

this is my first answer here, but I'll try my best.

I believe there's a misunderstanding about the relationship between ETH and the class EXP. The Exponential Time Hypothesis says that 3-SAT, a specific instance of SAT, cannot be solved in subexponential time. This implies that certain problems in NP require exponential time, but it does not imply NP=EXP.

To prove NP=EXP, you would need to show that every problem in EXP has a polynomial-time reduction to an NP-complete problem. ETH only provides a conjecture about the hardness of NP-complete problems under exponential time constraints, but not the equality you mentioned.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ but 3-SAT is NP, so therefore there is a polynomial time reduction from 3-SAT to any NP-hard problem. therefore if 3-SAT requires exponential time, so do all NP-hard problems. Am I at least coreect here? I guess I kind of assumed that "all NP hard problems take exponential time" implies NP=EXP, but I realise now that that isn't obvious, because there still might be exptime problems that cannot be polynomially checked. $\endgroup$
    – user56834
    Commented Jun 15 at 11:02
  • 1
    $\begingroup$ does NP=EXPTIME at least imply ETH? $\endgroup$
    – user56834
    Commented Jun 15 at 11:07
  • $\begingroup$ Yes, you are correct there. Regarding your realization this is not exactly the reason why the equality is not obtained. Think of it in this way: there might be harder problems in EXP than 3-SAT, such that even if you allow yourself to solve them in 3-SAT's complexity, it still wouldn't be enough. Thus, those problems are not in NP. Regarding your second statement - no, it doesn't imply either. This wouldn't give you any new information about 3-SAT, as you already know it's in NP and thus also in EXP. $\endgroup$
    – nicolas duek
    Commented Jun 15 at 11:29
  • 2
    $\begingroup$ NP=E implies ETH, because: 1)Every E-complete problem requires $\Omega(a^n)$ for some constant $a>1$ time to solve. 2) There is a polynomial time reduction from an EXP-complete problem to 3-SAT, which means 3-SAT requires at least exponential time to solve (otherwise the reduction would violate the point 1). As for NP=EXP, it could be still the case that e.g. 3- SAT is solvable in time $O(2^{\sqrt n})$. $\endgroup$
    – rus9384
    Commented Jun 15 at 14:32
  • 1
    $\begingroup$ What is the difference between NP=E and NP=EXP? $\endgroup$
    – user56834
    Commented Jun 15 at 15:26

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.