<p>If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice though that, in general, encoding the input for $n$-variable 3-SAT or $n$-vertex 3-COLORING takes something like $O(n\log n)$ bits. For example, to describe a sparse graph as input to 3-COLORING, for each edge we would have to list its endpoints. So the lower bound is not exponential in the length of the input. Therefore, my question is the following:</p>

<p>Is there a problem for which no $2^{o(n)}$ algorithm exists for inputs of length $n$ bits (assuming ETH)?</p>

<p>Ideally, the problem would be in NP (no cheating with succinct NEXP-hard problems!) and be reasonably natural, but I won't be picky.</p>

<p>Let me also note that after digging around I found that there are efficient ways to encode planar graphs with $O(n)$ bits. So, if one could find a problem that takes time exponential in the number of vertices even for planar graphs, the question would be settled. However, because planar graphs have treewidth $O(\sqrt{n})$, most natural problems have sub-exponential algorithms in this case.</p>

CC BY-SA 3.0
2013-01-20T23:18:16.270Z
If you are fine with dropping the condition that the problem is in NP, then you can use any undecidable problem and you do not even need the exponential time hypothesis.  So probably you should be picky.
Tsuyoshi Ito
CC BY-SA 3.0
2013-01-21T06:33:43.773Z
A problem in NP for which our present algorithmic knowledge is consistent with such a ETH result is edge chromatic number in a dense graph. AFAIK, we do not yet know of any $2^{o(|E|)}$ time algorithms...
Andreas Björklund
CC BY-SA 3.0
2013-01-21T13:36:28.917Z
It is probably not possible to compress $n$ variable SAT instances to $O(n \log n)$ as stated in the question (Dell, van Malkebeek, "Satisfibility Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses"). However, 3-SAT has no $2^{o(m)}$ algorithm where $m$ is the number of clauses, as shown by Impagliazzo and Paturi (assuming ETH). Since the hard cases have $O(m)$ variables we have $b=O(m \log m)$, so $m=\Omega(b/\log b)$, so 3-SAT has no $2^{o(b/\log b)}$ algorithm where $b$ is the input size.
Colin McQuillan
CC BY-SA 4.0
2018-08-16T15:22:44.807Z
Can you point to a reference where I can find efficient ways to encode planar graphs with O(n) bits? (I assume that n is the number of vertices). If so, there are NP-Complete problems for planar graphs and maybe the problem can also be presented in O(n) bits using these methods. Thanks.
Avi Tal
CC BY-SA 4.0
2018-09-13T15:16:27.040Z
Would disordered lattice tiling work? Without disorder the problem is NEXP-complete [arXiv:0905.2419] but with disorder (e.g., a vertex-dependent constraint on the tiles) the input would need to be $O(n)$. This is reasonably natural: it would arise in physics as the zero-temperature partition function of a disordered vertex model.
delete000
CC BY-SA 4.0
2018-09-22T13:26:54.890Z
@AviTal This paper comes to mind https://arxiv.org/abs/cs/0102005 . The usual keywords for this line of research seem to be "compact" and "succinct" encodings or representations. (succinct is stronger in that it is optimal up to an additive term instead of a multiplicative factor for compact).
A.N.
CC BY-SA 4.0
2020-01-05T22:34:12.810Z
How about the following problem, for some large constant $c>0$?  Given the encoding of a non-deterministic TM $M$ and binary string $w$, does $M(w)$ have an accepting computation of length at most $|w|^c$?  This should work if anything does... (?)
Neal Young
CC BY-SA 4.0
2023-11-13T01:26:37.063Z
I believe that it is an open question if we can have a lower bound $2^{\Omega(n)}$ under ETH, where $n$ is the bit size. We know that proving lower bound $\Omega(c^n)$ under SETH would disprove SETH.
ivmihajlin
<cc.complexity-theory><sat><planar-graphs><succinct>
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
Michael Lampis
# Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?

(Asked by: username_0 on 2013-01-19)

If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice though that, in general, encoding the input for $n$-variable 3-SAT or $n$-vertex 3-COLORING takes something like $O(n\log n)$ bits. For example, to describe a sparse graph as input to 3-COLORING, for each edge we would have to list its endpoints. So the lower bound is not exponential in the length of the input. Therefore, my question is the following:

Is there a problem for which no $2^{o(n)}$ algorithm exists for inputs of length $n$ bits (assuming ETH)?

Ideally, the problem would be in NP (no cheating with succinct NEXP-hard problems!) and be reasonably natural, but I won't be picky.

Let me also note that after digging around I found that there are efficient ways to encode planar graphs with $O(n)$ bits. So, if one could find a problem that takes time exponential in the number of vertices even for planar graphs, the question would be settled. However, because planar graphs have treewidth $O(\sqrt{n})$, most natural problems have sub-exponential algorithms in this case.

**Tags:** cc.complexity-theory, sat, planar-graphs, succinct
> **Comments:**
> **username_1**: If you are fine with dropping the condition that the problem is in NP, then you can use any undecidable problem and you do not even need the exponential time hypothesis.  So probably you should be picky.  
> **username_2**: A problem in NP for which our present algorithmic knowledge is consistent with such a ETH result is edge chromatic number in a dense graph. AFAIK, we do not yet know of any $2^{o(|E|)}$ time algorithms...  
> **username_3**: It is probably not possible to compress $n$ variable SAT instances to $O(n \log n)$ as stated in the question (Dell, van Malkebeek, "Satisfibility Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses"). However, 3-SAT has no $2^{o(m)}$ algorithm where $m$ is the number of clauses, as shown by Impagliazzo and Paturi (assuming ETH). Since the hard cases have $O(m)$ variables we have $b=O(m \log m)$, so $m=\Omega(b/\log b)$, so 3-SAT has no $2^{o(b/\log b)}$ algorithm where $b$ is the input size.  
> **username_4**: Can you point to a reference where I can find efficient ways to encode planar graphs with O(n) bits? (I assume that n is the number of vertices). If so, there are NP-Complete problems for planar graphs and maybe the problem can also be presented in O(n) bits using these methods. Thanks.  
> **username_5**: Would disordered lattice tiling work? Without disorder the problem is NEXP-complete [arXiv:0905.2419] but with disorder (e.g., a vertex-dependent constraint on the tiles) the input would need to be $O(n)$. This is reasonably natural: it would arise in physics as the zero-temperature partition function of a disordered vertex model.  
> **username_6**: @AviTal This paper comes to mind https://arxiv.org/abs/cs/0102005 . The usual keywords for this line of research seem to be "compact" and "succinct" encodings or representations. (succinct is stronger in that it is optimal up to an additive term instead of a multiplicative factor for compact).  
> **username_7**: How about the following problem, for some large constant $c>0$?  Given the encoding of a non-deterministic TM $M$ and binary string $w$, does $M(w)$ have an accepting computation of length at most $|w|^c$?  This should work if anything does... (?)  
> **username_8**: I believe that it is an open question if we can have a lower bound $2^{\Omega(n)}$ under ETH, where $n$ is the bit size. We know that proving lower bound $\Omega(c^n)$ under SETH would disprove SETH.  

---

## 0 answers

