Tag
reductions
- Oct 19, 2026 Ambiguity, Equivalence, and Other Undecidable Grammar Questions Membership in a context-free language is decidable, but asking whether two grammars denote the same language is not, and neither is asking whether one is ambiguous. computation theory
- Mar 12, 2026 Rice’s Theorem and the Collapse of Semantic Properties Why every nontrivial property of the language a program computes is undecidable, how the proof smuggles a halting question into an arbitrary property, and which program properties escape the theorem. computation theory
- Dec 29, 2025 From Heuristic Hashes to the Random Oracle Model Why hash-based proofs are stated against an idealised function, what a reduction actually guarantees when the real hash is used instead, and where the modelling assumption fails. cryptography
- Nov 10, 2025 The Post Correspondence Problem as a Reduction Source How a set of domino pairs encodes a computation through matched strings, why no algorithm can decide whether a match exists, and why this formulation is the convenient origin for other undecidability proofs. 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
- Dec 9, 2024 Mapping Reductions and the Halting Problem How a computable function that maps one language into another transfers undecidability, why the halting problem follows from acceptance by a reduction in the opposite direction, and where the construction breaks. computation theory