<p>An 'easy' SAT case (although not expressed by the clause to variable ratio) is this:</p>
<p>A <span class="math-container">$k$</span>-SAT formula is satisfiable if every clause overlaps with at most <span class="math-container">$2^{k-2}$</span> 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-Tardos algorithm.</p>
<p>For a survey about the Lovasz Local Lemma (including the derivation of this result), see the following <a href="https://www.mdpi.com/1999-4893/14/12/355" rel="nofollow noreferrer">paper</a>.</p>

CC BY-SA 4.0
2022-01-25T07:10:45.657Z
Thank you. That is a nice result. But as you mentioned it doesn't directly address the c/v ratio query. I am aware that the problem instances seem to show a phase transition for random 3-SAT instances at around 4.3 (https://cstheory.stackexchange.com/questions/4375/which-sat-problems-are-easy) but I was wondering if there is a similar result for the easy cases as well (without any need to have the additional randomness constraint i.e. without requiring anything else about the structure of the problem).
TheoryQuest1
CC BY-SA 4.0
2022-01-25T00:00:09.050Z
2022-01-25T00:00:09.050Z
Andras Farago
<p>Given the 3-SAT problem with <span class="math-container">$v$</span> variables and <span class="math-container">$c$</span> clauses:</p>
<p>Is there a clause to variable ratio for which the 3SAT problem is 'easy' i.e. solvable in polynomial time?</p>
<p>We are assuming the 3-SAT instances are not trivially separable. We define a 3-SAT instance as separable if it can be separated into two subset of clauses <span class="math-container">$c_0$</span> and <span class="math-container">$c_1$</span> (<span class="math-container">$c=c_0+c_1$</span>) such that <span class="math-container">$c_0$</span> and <span class="math-container">$c_1$</span> have no common variables (i.e. they are effectively two separate 3-SAT instances).</p>
<p>The above assumption is to avoid adding dummy clauses and variables to adjust the clause to variable ratio for any given problem instance.</p>

CC BY-SA 4.0
2022-01-24T20:41:33.490Z
Cross-posted: https://cs.stackexchange.com/q/148656/755, https://cstheory.stackexchange.com/q/51026/5038.  [Do not post the same question simultaneously on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
CC BY-SA 4.0
2022-01-24T20:42:12.930Z
Something seems to be missing in the end of the question - copy-paste failure, I guess.
D.W.
CC BY-SA 4.0
2022-01-25T11:11:52.233Z
I thought I deleted the other Q (before posting here). Apologies. Please let this one be open as the other one is deleted!
TheoryQuest1
CC BY-SA 4.0
2022-01-26T07:24:45.660Z
Padding can still be used to get the clause:variable ratio $r$ of hard instances down to $1/2+o(1)$: pick an arbitrary variable $x$ from an NP-hard inseparable instance, and tack on $\omega(m)$ clauses of the form $(x\vee v_1\vee v_2)$ where $v_1$ and $v_2$ are new, unique variables. This is asymptotically as low as $r$ can get for inseparable instances.
Yonatan N
CC BY-SA 4.0
2022-01-26T07:50:03.393Z
@YonatanN can you please elaborate on the above answer. 1. what is $\omega(m)$ here is unclear? 2. It is unclear the kind of clauses we are adding. Does that mean for a 3-SAT variable $x$ we create two new variables for each clause and add a clause $(x\vee v_1\vee v_2)$? Why will that work? 3. Most importantly "This is asymptotically as low as r can get for inseparable instances."  Can you please provide a justification or a proof? The query was does a clause to variable ratio (assuming we are somehow magically able to transform the any given instance to that) makes the problem easy to solve?
TheoryQuest1
CC BY-SA 4.0
2022-01-26T11:52:38.120Z
For each of the $m$ clauses in the original hard instance, create $k$ new clauses that each reuse one variable in the original instance and introduce two variables not found in any other clause. You now have $(k+1)m$ clauses and $n+2km$ variables. Taking $k\gg n$, the limit as $k\rightarrow \infty$ of the ratio is thus $1/2$. This is asymptotically tight, as inseparable instances admit a simple enumeration over clauses such that each clause after the first introduces at most 2 new variables not seen in any previous clauses; hence there are at most $2m+1$ variables in total for such instances.
Yonatan N
CC BY-SA 4.0
2022-01-26T12:28:39.027Z
thank you! much more clearer. but the original query still seems unanswered as we we looking for the cases (c/v ratio) where the problem is 'easy'. i haven't found any result related to the same?
J.Doe
CC BY-SA 4.0
2022-01-26T15:36:12.680Z
The above (plus clause duplication) argues that we can construct hard inseparable instances for any constant ratio >1/2, and that there are no inseparable instances at all with a ratio smaller than 1/2. For ratio exactly 1/2, it turns out that every instance is satisfiable. For if there are 2m variables, then the above enumeration must introduce 3 new variables in the first clause, 2 new variables $m-2$ times, and only 1 new variable exactly once. In particular, each clause introduces some new variable. For each clause, set all variables that it introduced so that they make that clause true.
Yonatan N
<cc.complexity-theory><sat>
Polynomially solvable 3-SAT problem instances
TheoryQuest1
# Polynomially solvable 3-SAT problem instances

(Asked by: username_0 on 2022-01-24)

Given the 3-SAT problem with $v$ variables and $c$ clauses:

Is there a clause to variable ratio for which the 3SAT problem is 'easy' i.e. solvable in polynomial time?

We are assuming the 3-SAT instances are not trivially separable. We define a 3-SAT instance as separable if it can be separated into two subset of clauses $c\_0$ and $c\_1$ ($c=c\_0+c\_1$) such that $c\_0$ and $c\_1$ have no common variables (i.e. they are effectively two separate 3-SAT instances).

The above assumption is to avoid adding dummy clauses and variables to adjust the clause to variable ratio for any given problem instance.

**Tags:** cc.complexity-theory, sat

> **Comments:**
> **username_1**: Cross-posted: https://cs.stackexchange.com/q/148656/755, https://cstheory.stackexchange.com/q/51026/5038.  [Do not post the same question simultaneously on multiple sites](https://meta.stackexchange.com/q/64068).  
> **username_1**: Something seems to be missing in the end of the question - copy-paste failure, I guess.  
> **username_0**: I thought I deleted the other Q (before posting here). Apologies. Please let this one be open as the other one is deleted!  
> **username_2**: Padding can still be used to get the clause:variable ratio $r$ of hard instances down to $1/2+o(1)$: pick an arbitrary variable $x$ from an NP-hard inseparable instance, and tack on $\omega(m)$ clauses of the form $(x\vee v_1\vee v_2)$ where $v_1$ and $v_2$ are new, unique variables. This is asymptotically as low as $r$ can get for inseparable instances.  
> **username_0**: @YonatanN can you please elaborate on the above answer. 1. what is $\omega(m)$ here is unclear? 2. It is unclear the kind of clauses we are adding. Does that mean for a 3-SAT variable $x$ we create two new variables for each clause and add a clause $(x\vee v_1\vee v_2)$? Why will that work? 3. Most importantly "This is asymptotically as low as r can get for inseparable instances."  Can you please provide a justification or a proof? The query was does a clause to variable ratio (assuming we are somehow magically able to transform the any given instance to that) makes the problem easy to solve?  
> **username_2**: For each of the $m$ clauses in the original hard instance, create $k$ new clauses that each reuse one variable in the original instance and introduce two variables not found in any other clause. You now have $(k+1)m$ clauses and $n+2km$ variables. Taking $k\gg n$, the limit as $k\rightarrow \infty$ of the ratio is thus $1/2$. This is asymptotically tight, as inseparable instances admit a simple enumeration over clauses such that each clause after the first introduces at most 2 new variables not seen in any previous clauses; hence there are at most $2m+1$ variables in total for such instances.  
> **username_3**: thank you! much more clearer. but the original query still seems unanswered as we we looking for the cases (c/v ratio) where the problem is 'easy'. i haven't found any result related to the same?  
> **username_2**: The above (plus clause duplication) argues that we can construct hard inseparable instances for any constant ratio >1/2, and that there are no inseparable instances at all with a ratio smaller than 1/2. For ratio exactly 1/2, it turns out that every instance is satisfiable. For if there are 2m variables, then the above enumeration must introduce 3 new variables in the first clause, 2 new variables $m-2$ times, and only 1 new variable exactly once. In particular, each clause introduces some new variable. For each clause, set all variables that it introduced so that they make that clause true.  

---

## 1 answers

### Answer by username_4 on 2022-01-25. Score: 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-Tardos algorithm.

For a survey about the Lovasz Local Lemma (including the derivation of this result), see the following [paper](https://www.mdpi.com/1999-4893/14/12/355).

> **Comments:**
> **username_0**: Thank you. That is a nice result. But as you mentioned it doesn't directly address the c/v ratio query. I am aware that the problem instances seem to show a phase transition for random 3-SAT instances at around 4.3 (https://cstheory.stackexchange.com/questions/4375/which-sat-problems-are-easy) but I was wondering if there is a similar result for the easy cases as well (without any need to have the additional randomness constraint i.e. without requiring anything else about the structure of the problem).  

---

