1
$\begingroup$

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

Edited Major edit to address comments

$\endgroup$

closed as off-topic by David Richerby, Yuval Filmus, Discrete lizard, Evil, Andrej Bauer Jan 25 at 8:12

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Please don't invent your own terminology for standard concepts. "Contradiction" already has a meaning, and it is not the meaning that you're using. It's not reasonable to require everyone who reads your work to learn these new definitions, and this is exactly the sort of thing that causes papers to get rejected without any substantive comments. It's nearly impossible to check that somebody's work is correct if, every time they use a well-understood word like "contradiction", the reader has to remember that it actually means "falsifying assignment". $\endgroup$ – David Richerby Jan 24 at 17:02
  • 3
  • 3
    $\begingroup$ I'm voting to close this question as off-topic because it proposes a solution to the P vs NP problem. $\endgroup$ – Yuval Filmus Jan 24 at 18:47
  • 2
    $\begingroup$ I have attempted to read your question again, but it is not written in a way I can understand. I suggest you rewrite your answer and take the following into account: 1. Start your answer with a complete and formal definition of your conjecture, leave examples and arguments in favor or against your conjecture until the end of your question. You may wish to define other concepts to aid in stating your conjecture, but be sure to properly define all terms you use. In particular, you should define 'k-contradiction' and 'm'. This way, your main problem should be clear. $\endgroup$ – Discrete lizard Jan 25 at 17:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Discrete lizard Jan 25 at 17:30