# Could you show the intractibility of SAT by showing that the number of variables contributing to an arbitrary unsatisfied clause is not constant? [closed]

Preface: This is not an attempted proof at P vs NP

Starting with some CNF Boolean expression ϕ, by the rules of logical disjunction, a clause is only unsatisfied if each of the literals in it are themselves forced into being unsatisfied. A trivial example is (x OR y) with the interpretation XY=00. Non-trivially, we can find a contradiction, ϕ ↔ x ∧ -x. Since a Boolean variable can only be true or false, some clause in ϕ will remain unsatisfied depending on which interpretation of X we choose.

ϕ is satisfied by an interpretation I, iff I doesn't leave any of the clauses in ϕ unsatisfied, following the rules of logical conjunction. If each I contains some unsatisfied clause, then ϕ is unsatisfiable.

ϕ = (a OR c) AND (b OR d) AND (-c OR -d)
ϕ[00CD] = (0 OR c) AND (0 OR d) AND (-c OR -d)

Due to the clausal structure of ϕ above, any I containing A=0 and B=0 will always force the expression into being unsatisfied. Even if we add more clauses or more variables, the existence of these clauses in ϕ means that any such I will always be an unsatisfying interpretation.

Following from this, if ϕ also contained clauses which acted analogously on interpretations containing AB=01, AB=10, or AB=11, then there'd be no satisfying assignment containing A and B. Since all maximal interpretations will contain some assignment for A and B, ϕ is made unsatisfiable based off of these 2, out of a potential n, variables.

ϕ' = (a OR b) AND (a OR c) AND (-b OR -c)
ϕ'' = (-a OR d) AND (-a OR e) AND (-d OR -e)

We could create an example with 1 variable as well. ϕ' has no satisfying I which contains A=0 and ϕ'' has no satisfying I which contains A=1, as the respective assignment to A allows us to generate a contradiction in that expression. If we have the expression Φ = ϕ' AND ϕ'', then we'd automatically have an unsatisfiable expression caused by the complete inability to assign A.

So could we tie up 3, 4, 5 or m $$\le$$ n variables such that each of the 2m ways of assigning them forces some unsatisfied clause? If m is the maximum number of variables which we could tie up to force some arbitrary clause of size k into being unsatisfied, then if you take each of the (n choose m) possible groups of variables and you try all 2m ways of assigning them, as long as each variable group has at least one I which doesn't leave some clause unsatisfied, then your expression is satisfiable.

I conjecture that when k = 2, m = 2, no matter the problem instance. This would mean that no group of 3 or more variables is both necessary and sufficient to leave a clause with only 2 literals unsatisfied. However, once k $$\ge$$ 3, then m $$\le$$ n. We could force a clause of 3 literals to be unsatisfied with 3, 4, or 5 variables, only bounded by n or the total number of variables in ϕ.

I have not given any proof that 2SAT and 3SAT have the value of m that I think they do, but what I want to know is if the conjecture is true, would that mean that the classes are different? Would such a structural difference, if proven to be true, be able to separate the two classes of problems?

Edited to create a more technical question to clarify the information I'm looking for

• 2. Try to avoid redefining existing terms, this confuses people to no end. Perhaps you can call $x\wedge \neg x$ a contradicting pair and go from there. 3. Try to use MathJax for your formulas. If you have done this, there is a much larger chance that we will be able to help you than for this question in its current form. – Discrete lizard Jan 25 '19 at 17:30