Attack notebook 02: change the proof language
Status: explicit toy calculation, not a complexity separation and not a claimed proof of P versus NP.
Approach
Study graph parity constraints (Tseitin formulas) as a laboratory for resolution lower bounds. Resolution manipulates clauses; linear algebra manipulates parity equations. A lower bound for the former need not constrain the latter.
Checkable toy instance
Take a triangle with edge variables x, y, z. Put charge 1 at the first vertex and charge 0 at the other two. Its vertex equations over the field with two elements are:
- x + z = 1
- x + y = 0
- y + z = 0
Adding all three equations cancels every edge variable twice. The resulting equation is 0 = 1. This establishes that this toy instance has no satisfying assignment.
The same constraints in conjunctive normal form are:
- (x ∨ z) and (¬x ∨ ¬z)
- (¬x ∨ y) and (x ∨ ¬y)
- (¬y ∨ z) and (y ∨ ¬z)
Each pair says respectively that its variables differ, agree, and agree.
Short resolution refutation
Resolve (x ∨ z) with (¬y ∨ z) on z to obtain (x ∨ ¬y). Correction: these two clauses both contain positive z and cannot be resolved on z. That tempting move is invalid. Use the following actual derivation instead:
- Resolve (x ∨ z) with (y ∨ ¬z) on z: obtain (x ∨ y).
- Resolve (x ∨ y) with (x ∨ ¬y) on y: obtain x.
- Resolve (¬x ∨ ¬z) with (¬y ∨ z) on z: obtain (¬x ∨ ¬y).
- Resolve (¬x ∨ ¬y) with (¬x ∨ y) on y: obtain ¬x.
- Resolve x with ¬x: obtain the empty clause.
Repeated literals are identified in each resolvent. All starting clauses occur in the displayed CNF. These steps can be checked directly; no solver run is being claimed.
Dead ends and scope
- Odd total charge is not general SAT hardness. Summing the equations exposes the contradiction immediately. Gaussian elimination handles arbitrary systems of parity equations in polynomial time.
- This triangle is not an expander lower-bound example. It has a short resolution refutation too. It tests the encoding and inference rules, not asymptotic hardness.
- Irrelevant padding does not hide a short refutation. Adding unused variables or unrelated clauses leaves the original derivation available.
- The generalization fails: even a genuine resolution lower bound for larger graph formulas would not establish hardness for every SAT algorithm. These formulas retain their linear-algebra escape hatch.
Known-barrier audit
The immediate obstacle here is restricted-system scope: resolution does not model all efficient reasoning. Relativization, natural proofs, and algebrization constrain particular families of broader approaches; merely naming them does not establish that this toy argument evades them.
Best partial result
An explicit parity-to-CNF encoding and two independently checkable refutations of a toy instance: equation summation and resolution. This is an educational sanity check, not a novel research result.
Next attack
Study what changes when parity constraints are coupled to nonlinear constraints. Candidate question: can a precisely defined family defeat a specified parity-aware procedure, rather than silently assuming it defeats all polynomial-time algorithms? First specify that procedure and its allowed inferences; then search for counterexamples to the claim before pursuing a lower bound.
Break this notebook: check the CNF encoding and every resolvent. Any stronger hardness claim requires a formal model, a growing family, and an asymptotic argument.