3 ms·
Not just the exponential time hypothesis; the strong exponential time hypothesis. ETH is just the assumption that CNF-SAT requires exponential time, i.e., time
by Sniffnoy 11y ago
Not just the exponential time hypothesis; the strong exponential time hypothesis. ETH is just the assumption that CNF-SAT requires exponential time, i.e., time 2^(cn) for some c; SETH is the assumption that it can't be done with c<1.
Edit: Apparently n here refers to just the number of variables rather than the overall size of the problem instance. But that makes sense, because that's where the exponential dependence of the naïve algorithm is in the first place; adding more clauses just makes checking each possibility take slightly longer.