id: 01642222
dt: j
an: 01642222
au: Impagliazzo, Russell; Paturi, Ramamohan
ti: On the complexity of $k$-SAT.
so: J. Comput. Syst. Sci. 62, No.2, 367-375 (2001).
py: 2001
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: $k$-SAT problem; critical clauses; Sparsification Lemma
ci: 
li: doi:10.1006/jcss.2000.1727
ab: Summary: The $k$-SAT problem is to determine if a given $k$-CNF has a
    satisfying assignment. It is a celebrated open question as to whether
    it requires exponential time to solve $k$-SAT for $k\ge 3$. Here
    exponential time means $2^{δn}$ for some $δ> 0$. In this paper,
    assuming that, for $k\ge 3$, $k$-SAT requires exponential time
    complexity, we show that the complexity of $k$-SAT increases as $k$
    increases. More precisely, for $k\ge 3$, define $s_k= \inf\{δ$: there
    exists $2^{δn}$ algorithm for solving $k$-SAT\}. Define ETH
    (Exponential-Time Hypothesis) for $k$-SAT as follows: for $k\ge 3$,
    $s_k> 0$. In this paper, we show that $s_k$ is increasing infinitely
    often assuming ETH for $k$-SAT. Let $s_\infty$ be the limit of $s_k$.
    We will in fact show that $s_k\le (1-d/k)s_\infty$ for some constant
    $d> 0$. We prove this result by bringing together the ideas of critical
    clauses and the Sparsification Lemma to reduce the satisfiability of a
    $k$-CNF to the satisfiability of a disjunction of $2^{εn}$ $k’$-CNFs
    in fewer variables for some $k’\ge k$ and arbitrarily small $ε> 0$.
    We also show that such a disjunction can be computed in time $2^{εn}$
    for arbitrarily small $ε> 0$.
rv: