New answers tagged sat
1
An 'easy' SAT case (although not expressed by the clause to variable ratio) is this:
A $k$-SAT formula is satisfiable if every clause overlaps with at most $2^{k-2}$ other clauses in it. Overlap means sharing the same variable. This result follows from the Lovasz Local Lemma. In this case a satisfying assignment can also be found efficiently by the Moser-...
5
Theorem 1. For all $n\ge 6$ and $T$ with $n+14\le T \le 7{n\choose 3}$, there is a satisfiable 3-SAT formula on $n$ variables with $T$ clauses in which all clauses are redundant.
Before we give the proof, note that $7{n\choose 3}$ is an upper bound on the number of clauses in any satisfiable 3-CNF formula. In the case $T=7{n\choose 3}$ the theorem implies ...
5
I interpret the question as: given $n$ and $T$, what is the maximum number of redundant clauses a satisfiable $n$-variable formula on $T$ clauses can have?
For the purposes of this question, I find it helpful to phrase this as:
Find (lower bounds on) $f(n,m)$ such that an $n$-variable $m$-clause formula may imply $f(n,m)$ clauses (that may or may not be in ...
Top 50 recent answers are included