8
$\begingroup$

Let SAT$_v$ be the language of those instances of SAT that contain variables $[v] = \{0,1,\dots,v-1\}$, let $k$-SAT be the language of those instances of SAT in which every clause has at most $k$ literals, and let $k$-SAT$_v$ be their intersection. Let $s_k = \inf_M\{\delta \mid \exists c\forall v\;( M\text{ decides } k\text{-SAT$_v$ in }2^{v\delta-c})\text{ time}) \}$, where the infimum ranges over all algorithms (machines in some model of computing). Let $s_\infty = \lim_{k \to \infty} s_k$. For this to make sense, one has to assume that there is a reasonable bound on the size of the input in terms of the number of variables; otherwise one could repeat clauses to force $s_k$ and $s_\infty$ to be as large as desired. So assume clauses are not repeated.

Note that each $k$-CNF formula then has size at most $O(v^k)$, so the size of the input formula is not important when considering an exponent that is linear in $v$. It then follows that $s_3 \le s_4 \le \dots \le s_\infty$.

The Exponential Time Hypothesis (ETH) is the statement that $s_k > 0$ for some $k\ge 3$. The sequence $(s_k)$ increases infinitely often if ETH holds. The Strong ETH (SETH) is the statement that $s_\infty \ge 1$ or $s_\infty = 1$, depending on which reference one uses.

In contrast, each instance of SAT$_v$ contains up to $3^v$ distinct clauses (each variable can be positive, negative, or absent in each clause). Hence an input may have length $\Omega(2^{n\log 3})$ even if no clause is repeated, so this is a lower bound for the time to read the input, and then also for the overall time.

If we then let $s_\omega = \inf_M\{\delta \mid \exists c\forall v\;( M\text{ decides } \text{SAT$_v$ in }2^{v\delta-c})\text{ time}) \}$, it is clear that $s_\omega \ge \log 3 \gt 1.58$ just by considering the input sizes. Even if one requires an input formula to contain no clause that is subsumed by another, $s_\omega \ge 1.5$. By the trivial algorithm, it is also the case that $s_\omega \le 1+\log 3$.

Why is there a gap between $s_\infty$ and $s_\omega$, assuming SETH?

In some sense $s_\omega$ is just a different way to take the limit, so it seems puzzling that there should be a gap.

  • Russell Impagliazzo and Ramamohan Paturi, On the Complexity of $k$-SAT, JCSS 62 367–375, 2001. doi:10.1006/jcss.2000.1727 (preprint)
  • Evgeny Dantsin and Alexander Wolpert, On Moderately Exponential Time for SAT, SAT 2010, LNCS 6175 313–325. doi:10.1007/978-3-642-14186-7_27 (preprint)
  • Chris Calabro, Russell Impagliazzo and Ramamohan Paturi, The Complexity of Satisfiability of Small Depth Circuits, IWPEC 2009, LNCS 5917 75–85. doi:10.1007/978-3-642-11269-0_6 (preprint)
  • Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström, On Problems as Hard as CNF-SAT, arXiv:1112.2275v3, 27 Mar 2014.
$\endgroup$
6
$\begingroup$

The difference between your definitions is that the clause width in $s_\omega$ is allowed to grow with the number of variables, while for $s_\infty$ it is arbitrarily large but constant.

It's a similar issue as PH vs PSPACE. If you take an arbitrary constant number of quantifier alterations you get the polynomial hierarchy, but if you allow the formula to be fully quantified you get a PSPACE-complete problem.

$\endgroup$
4
$\begingroup$

A better way to define these exponents is if you ask about the running time in the form $c^n\cdot poly(|F|)$, where $poly(|F|)$ is an arbitrary polynomial of the input size. Then artifacts like the $3^v$ size disappear.

$\endgroup$
  • $\begingroup$ That seems like a sensible approach motivated by parameterized complexity. However, the papers dealing with ETH either seem to leave it quite vague, or use a definition that is essentially the one I provide above. Do you have a pointer? $\endgroup$ – András Salamon May 3 '15 at 12:21
  • $\begingroup$ When we talk about k-SAT, it does not matter, because the formula size is polynomial in the number of variables. Regarding pointers, look, for example, how Impagliazzo, Paturi, and Zane define the class SE in "Which Problems Have Strongly Exponential Complexity?", Journal of Computer and System Sciences 63, 512–530 (2001). $\endgroup$ – hirsch May 4 '15 at 12:38
  • $\begingroup$ Thanks, that's useful; I have previously only really focused on the Sparsification Lemma from that paper. $\endgroup$ – András Salamon May 4 '15 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.