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)$?

  • $\begingroup$ Do you mean random dense SAT instances? $\endgroup$ Jul 10, 2023 at 2:41
  • $\begingroup$ 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... $\endgroup$ Jul 10, 2023 at 16:54
  • $\begingroup$ @PeterShor I mean the worst-case complexity for the problem like "This SAT instance has density $\le\alpha$ and is satisfiable. $\endgroup$
    – rus9384
    Jul 11, 2023 at 20:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.