Complexity Reductions & Decidability

← Back to Domain-Specific Families

Abstractions about approximation, computational reductions, satisfiability procedures, undecidability, complexity separations, and total programming.

10 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Approximation Algorithm — A polynomial-time optimization algorithm that always returns a feasible solution with a proved worst-case quality bound relative to the optimum.
• Davis–Putnam Algorithm — Decide clausal satisfiability by eliminating variables with resolution while preserving whether the clause set has a model.
• Halting Problem — Turing's proof that no general algorithm can decide, for every program-input pair, whether the program halts or loops forever — established by a diagonal argument that builds an adversary doing the opposite of any claimed decider's prediction about itself.
• L-Reduction — Transfer approximation guarantees and hardness between optimization problems through polynomial instance and solution maps whose two fixed-constant inequalities control optimum scale and solution-error distortion.
• P versus NP Problem — Ask whether every problem whose solutions can be verified in polynomial time can also be solved in polynomial time — turning the apparent gap between checking and finding into the open question of whether it is a structural barrier (P ≠ NP) or mere ignorance (P = NP).
• Pseudo-polynomial transformation — Map instances between numerical decision problems while preserving yes/no membership and polynomially controlling computation, encoding growth, and the target's largest numerical parameter.
• PTAS Reduction — Transfer a polynomial-time approximation scheme from a target optimization problem back to a source problem by polynomial instance and solution maps whose parameter translation preserves every requested approximation tolerance.
• Reduction (Computability Theory) — Compare decision sets by an effective procedure that converts access to a solver for B into a solver for A, with the allowed access defining the reducibility notion.
• Rice's Theorem — Every non-trivial semantic property of programs — anything depending on the input-output function rather than the source text — is undecidable, proved by a generic reduction from the halting problem, so no exact analyzer for such a property can exist.
• Total functional programming — Restrict functional programs to total functions whose evaluation is defined and terminating for every input admitted by their types.