2003/01/20 by Russell Impagliazzo, Ramamohan Paturi · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Constraint Satisfaction and Optimization #Discrete mathematics #Exponential function #Infimum and supremum #Limit (mathematics) #Mathematical analysis #Mathematics #Sequence (biology)
paper · doi:10.1109/ccc.1999.766282
openalex publication_date 2003/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
The problem of k-SAT is to determine if the given k-CNF has a satisfying solution. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k/spl ges/3. Define s/sub k/ (for k/spl ges/3) to be the infimum of /spl delta/: there exists an O(2/sup /spl delta/n/) algorithm for solving k-SAT. Define ETH (Exponential-Time Hypothesis) for k-SAT as follows: for k/spl ges/3, s/sub k/>0. In other words, for k/spl ges/3, k-SA does not have a subexponential-time algorithm. In this paper we show that s/sub k/ is an increasing sequence assuming ETH for k-SAT: Let s/sub /spl infin// be the limit of s/sub k/. We in fact show that s/sub k//spl les/(1-d/k) s/sub /spl infin// for some constant d>0.