<p>By &quot;dense&quot; I mean instances in which the ratio of variables to clauses is below the critical threshold <span class="math-container">$2^k\ln2−\frac{(1+\ln2)}2+\epsilon_k$</span> for <span class="math-container">$k$</span>-SAT. For general SAT, however, I suppose this does not apply and instead you'd need to count density using clause weights <span class="math-container">$w(c)=2^{1-|c|}$</span> where <span class="math-container">$|c|$</span> is the width of the clause.</p>
<p>For any given SAT instance let's denote its set of variables with <span class="math-container">$V$</span> and its set of clauses with <span class="math-container">$C$</span> .</p>
<p>For SAT instances in which <span class="math-container">$\frac{|V|}{\sum_{\forall c\in C}w(c)}&lt;\alpha$</span> for some <span class="math-container">$\alpha$</span>, is there a (deterministic or probabilistic) algorithm that solves all of them in time <span class="math-container">$o(2^n)$</span>?</p>

CC BY-SA 4.0
2023-07-10T02:41:36.997Z
Do you mean random dense SAT instances?
Peter Shor 
CC BY-SA 4.0
2023-07-10T16:54:45.320Z
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...
Ryan Williams
CC BY-SA 4.0
2023-07-11T20:30:08.243Z
@PeterShor I mean the worst-case complexity for the problem like "This SAT instance has density $\le\alpha$ and is satisfiable.
rus9384
<cc.complexity-theory><time-complexity><sat>
Can "dense" SAT instances be solved in time $o(2^n)$?
rus9384
# Can "dense" SAT instances be solved in time $o(2^n)$?

(Asked by: username_0 on 2023-07-08)

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

**Tags:** cc.complexity-theory, time-complexity, sat
> **Comments:**
> **username_1**: Do you mean random dense SAT instances?  
> **username_2**: 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...  
> **username_0**: @PeterShor I mean the worst-case complexity for the problem like "This SAT instance has density $\le\alpha$ and is satisfiable.  

---

## 0 answers

