# Can "dense" SAT instances be solved in time $o(2^n)$?

By "dense" I mean instances in which the ratio of variables to clauses is below the critical threshold $$2^k\ln2−\frac{(1+\ln2)}2+\epsilon_k$$ for $$k$$-SAT. For general SAT, however, I suppose this does not apply and instead you'd need to count density using clause weights $$w(c)=2^{1-|c|}$$ where $$|c|$$ is the width of the clause.

For any given SAT instance let's denote its set of variables with $$V$$ and its set of clauses with $$C$$ .

For SAT instances in which $$\frac{|V|}{\sum_{\forall c\in C}w(c)}<\alpha$$ for some $$\alpha$$, is there a (deterministic or probabilistic) algorithm that solves all of them in time $$o(2^n)$$?

• Do you mean random dense SAT instances? Commented Jul 10, 2023 at 2:41
• Using the nomenclature from random k-SAT, you want the ratio of clauses to variables, not the other way around... and for "dense" you probably want to consider instances above this threshold... Commented Jul 10, 2023 at 16:54
• @PeterShor I mean the worst-case complexity for the problem like "This SAT instance has density $\le\alpha$ and is satisfiable. Commented Jul 11, 2023 at 20:30