47
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 20, 2013 at 23:18
  • 14
    $\begingroup$ 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... $\endgroup$
    – Andreas Björklund
    Commented Jan 21, 2013 at 6:33
  • 11
    $\begingroup$ 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. $\endgroup$
    – Colin McQuillan
    Commented Jan 21, 2013 at 13:36
  • $\begingroup$ 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. $\endgroup$
    – Avi Tal
    Commented Aug 16, 2018 at 15:22
  • 2
    $\begingroup$ @AviTal This paper comes to mind 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). $\endgroup$
    – A.N.
    Commented Sep 22, 2018 at 13:26

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.