Lesson 3.2 · Chapter 3: Pairs and three places

Pairs cannot make a knot; three places can

Use a majority vote to see why pairwise rules cannot define a logical knot.

From John Cullen’s knotlab guide

Explore the idea

Three allowed states vote for a forbidden one

Each row agrees with the forbidden target on a different pair of bits. Take the majority separately in each column.

Allowed witnesses
A	B	c
0	1	0
1	0	0
1	1	1
?	?	?

Forbidden target: 110

? ? ?

Relations defined by 2-CNF, including after forgetting witnesses, are closed under majority. These three allowed rows would force the forbidden row to be allowed too.

The intuition. Whatever a two-place rule says, it says about a pair. A system of two-place rules that must all hold is therefore known from its pairs. A knot shows nothing in any pair, so pairs can never pin one down. Three-place rules can.

Classical. Relations definable by 2-CNF, even with witnesses quantified away, are exactly those closed under the majority operation (Schaefer 1978). A majority-closed relation is the conjunction of its two-variable projections (Baker and Pixley 1975).
Hence no 2-CNF defines a knot. If one did, the knot would equal the conjunction of its pairwise projections. Those are all unconstrained, so it would allow everything, contradicting K1. More witnesses do not help. Proved (Lean) for three variables directly: for any target state, take allowed states agreeing with it on each pair; their majority is the target (no_two_cnf_defines_knot, majority_with_free_pairs_is_full).
Width 3 binds any number of loops. A chain of three-literal clauses joined by witnesses does it: w1 ∨ ¬L1 ∨ ¬L2, then w2 ∨ ¬w1 ∨ ¬L3, and so on, ending with ¬w(n−2) ∨ ¬Ln ∨ c. Each witness wi is forced exactly when the loops before it are all present, so it records that they are bound. Naming each partial parity does the same for parity. Proved (Lean): chain_defines_knot, parity_chain_defines_parity.
Without witnesses, a knot needs full width. A knot on m variables implies no clause on fewer than m of them, because every proper projection is unconstrained. Proved (here); Lean checks the three-variable case (no_clause_on_a_b and its two companions).

So 3 is the exact threshold. Width 2 is closed: pairwise in, pairwise out. Width 3 reaches every knot.

Reading. Two-place rules are logic, not topology. The first place where logic binds something that no part shows is the step from two-literal to three-literal clauses. This is a statement about what can be expressed, not about how hard anything is to compute. There are easy knots: the atom is a Horn clause, and Horn satisfiability takes linear time (lessons 4.1 and 4.2). So this boundary is not the boundary between P and NP, and nothing here addresses that question.