Revisions to What is the difference between NP=EXP and ETH, and what does the community believe about their truth?

Format complexity classes and "SAT" as words in MathJAX, not as products of letters; minor incidental copy editing

Source Link

1

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

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

As far as $SAT$$\mathit{SAT}$ goes, we know that $SAT$$\mathit{SAT}$ can be decided in time $O(2^n)$, so $SAT \in EXPTIME$$\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 $SAT$$\mathit{SAT}$ be decided. iI.e., there are no algorithms with run timeruntime, for example, $O(2^{({\log n})^2})$. This run time is not polynomial, but sub-exponential.

It is possible that $P=NP \neq EXPTIME$$\mathit{P} = \mathit{NP} \neq \mathit{EXPTIME}$. The first equality implies that ETH is false, as this means $SAT$$\mathit{SAT}$ has a poly-time algorithm.
It is possible that $P\neq NP$$\mathit{P} \neq \mathit{NP}$ and $NP \neq EXPTIME$$\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.
It is possible that $P\neq NP$$\mathit{P} \neq \mathit{NP}$ and $NP \neq EXPTIME$$\mathit{NP} \neq \mathit{EXPTIME}$, butbut ETH is false: For, for example, if $SAT$$\mathit{SAT}$ can be decided in $O(2^{({\log n})^2})$ time.
It is also possible that $P\neq NP = EXPTIME$$\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 bound. If they can be converted to $SAT$$\mathit{SAT}$ in poly-time, then $SAT$$\mathit{SAT}$ must also have an exponential lower-bound, which is basically ETH.

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.

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

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.

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

inequality to equality

Source Link

edited Jun 15 at 15:09

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.

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.
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.
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.
It is also possible that $P\neq NP = EXPTIME$. But the last inequalityequality 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.

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.

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.
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.
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.
It is also possible that $P\neq NP = EXPTIME$. But the last inequality 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.

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.

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

Source Link

created Jun 15 at 14:42

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.

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.
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.
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.
It is also possible that $P\neq NP = EXPTIME$. But the last inequality 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.

Stack Exchange Network

Return to Answer