Lesson 7.1 · Chapter 7: Sources and questions
What is classical and what is ours
Separate classical foundations, the program’s interpretation, and its research claims.
From John Cullen’s knotlab guide
- Classical:
- 2-CNF relations are the majority-closed ones (Schaefer 1978) and are determined by their pairs (Baker and Pixley 1975);
- three-place relations build every relation while two-place ones do not (Peirce's reduction thesis);
- least worlds of Horn clauses (van Emden and Kowalski 1976);
- Post's lattice and the Galois connection behind it (Post 1941; Geiger 1968; Bodnarčuk, Kalužnin, Kotov and Romov 1969);
- the compactness theorem;
- frustration (Toulouse 1977) and the MAX-2-SAT gadget (Garey, Johnson and Stockmeyer 1976);
- Tseitin formulas and their parity contradictions (Tseitin 1968);
- Borromean and Brunnian links in topology;
- the background that lessons 4.1, 5.1 and 6.1 define: 2-CNF decided in linear time (Aspvall, Plass and Tarjan 1979) and 3-CNF NP-complete (Cook 1971), counting perfect matchings and 2-CNF solutions #P-hard (Valiant 1979), planar matchings counted by Pfaffians (Kasteleyn 1967), and the Nullstellensatz proof system (Beame, Impagliazzo, Krajíček, Pitassi and Pudlák 1996).
- Ours, as reading:
- the knot test K1–K3, read on allowed states with erasure as forgetting;
- a binding is a constraint with no trace in any part, which vanishes when either loop is erased;
- loops, their open distinctions and their witnesses are the units;
- emergence begins at the first such binding;
- distinctions are the material and atoms are the bonds;
- a hidden bit has a depth.
- Ours, as results. The classifications and constants marked as proved here or in Lean are elementary. Several are classical facts in new language, and we give sources where we know them. The three notes contain results that are new as far as our searches found, and each note states its own novelty and folklore risk. See FINDINGS.md.
- Not implied:
- Requirements alone run in linear time, and requirements with choice are NP-complete. That locates where hardness enters, but says nothing about whether P equals NP.
- Nothing here is physics.
- The interpretation that coherent alternatives are co-real is an interpretation, and nothing is proved from it.