0

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.

J.Doe
  • 468
  • 2
  • 8
TheoryQuest1
  • 811
  • 5
  • 13
  • 4
    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. – D.W. Jan 24 '22 at 20:41
  • 3
    Something seems to be missing in the end of the question - copy-paste failure, I guess. – D.W. Jan 24 '22 at 20:42
  • 1
    I thought I deleted the other Q (before posting here). Apologies. Please let this one be open as the other one is deleted! – TheoryQuest1 Jan 25 '22 at 11:11
  • 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 Jan 26 '22 at 07:24
  • @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 Jan 26 '22 at 07:50
  • 1
    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 Jan 26 '22 at 11:52
  • 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 Jan 26 '22 at 12:28
  • 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 Jan 26 '22 at 15:36

1 Answers1

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.

Andras Farago
  • 11,396
  • 37
  • 70
  • 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 Jan 25 '22 at 07:10