Skip to main content
2 of 3
inequality to equality
Lisa E.
  • 555
  • 18

No, ETH is not equivalent to saying $NP=EXPTIME$.

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

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

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

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

  2. It is possible that $P\neq NP$ and $NP \neq 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 $P\neq NP$ and $NP \neq EXPTIME$, but ETH is false: For example if $SAT$ can be decided in $O(2^{({\log n})^2})$ time.

  4. It is also possible that $P\neq NP = 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 $SAT$ in poly-time, then $SAT$ must also have an exponential lower-bound, which is basically ETH.

Lisa E.
  • 555
  • 18