Tag
diagonalization
- 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
- Jan 21, 2026 Encoding Turing Machines and the Undecidability of Acceptance How a machine becomes a finite string, what a configuration record contains, and why diagonalization over that encoding rules out any decider for acceptance. computation theory
- Jan 22, 2025 Diagonalization and the Time Hierarchy Theorem How a machine that runs itself on its own description separates two time bounds, why the constructibility condition cannot be dropped, and what the theorem does not prove. computation theory
- Nov 1, 2024 Oracles, Relativization, and the Limits of Diagonalization How adding an oracle changes what a proof can see, why there are oracles that collapse P and NP and oracles that separate them, and what that implies for any argument that treats machines as black boxes. computation theory