Tag
np-completeness
- Oct 12, 2026 The Cook–Levin Tableau: Encoding a Computation as a Formula How a nondeterministic polynomial-time computation becomes a boolean formula whose satisfying assignments correspond exactly to accepting runs, and what the encoding costs in variables and clauses. computation theory
- Jan 28, 2026 Ladner's Theorem: Building Languages Between P and NP How to construct an NP language that is neither in P nor NP-complete assuming P differs from NP, using a slow diagonalization that delays each requirement until the padding is large enough. computation theory
- May 21, 2025 Many-One Reductions and What Completeness Requires The mechanics of Karp reductions, why hardness and completeness are different properties, and the closure conditions a class must satisfy for a complete problem to exist. computation theory
- Aug 4, 2023 Dependency Resolution as a Satisfiability Problem How version selection encodes into boolean clauses, why the decision problem is NP-complete, and what that bound predicts about real installs and about optimisation criteria. developer tools
- Jun 10, 2022 Why Three Literals Is the Pivot for Satisfiability The reduction from general CNF to 3-SAT, why 2-SAT is solvable in linear time while 3-SAT is complete, and how clause length controls the shape of the search space. computation theory