many-one reducibility

many-one reducibility
Name	many-one reducibility
Field	Alan Turing-era Computability theory, Computational complexity theory
Introduced	Emil Post (conceptual predecessors), formalized in Stephen Cook-era literature
Notable	Post correspondence problem, Hilbert's tenth problem, Cook–Levin theorem

many-one reducibility

Many-one reducibility is a formal relation between decision problems used in Computability theory and Computational complexity theory to compare relative difficulty; it connects notions from Alan Turing's oracle studies, Emil Post's degrees, and later work by Stephen Cook and Richard Karp on NP-completeness. The relation is central to classifications such as Turing degree, m-degree, and the framework behind the Cook–Levin theorem, informing results about problems like the Post correspondence problem, Hilbert's tenth problem, and languages studied by John Rice and Noam Chomsky.

Definition

A set A is many-one reducible to a set B (written A ≤m B) if there exists a computable total function f such as those considered by Alan Turing and Alonzo Church that transforms instances of A into instances of B with preservation of membership; equivalently, for every x, x ∈ A iff f(x) ∈ B. The reduction concept relies on effective transducers studied by Emil Post, effective enumerability introduced by Kurt Gödel and Alonzo Church, and the recursive function machinery developed by Stephen Kleene and Michael Rabin.

Examples

Classic examples include the reduction of the Post correspondence problem to various tiling problems influenced by Hao Wang, reductions among Diophantine sets arising from work on Hilbert's tenth problem by Yuri Matiyasevich, Julia Robinson, and Martin Davis, and the many-one completeness proofs in Stephen Cook and Richard Karp's catalogs showing problems like SAT, CLIQUE, and HAMILTONIAN CYCLE are interreducible under many-one reductions. Other illustrative instances appear in lattice problems studied by Miklós Ajtai and László Lovász, as well as word problems for group theory groups analyzed by Max Dehn and Graham Higman.

Properties and basic results

Many-one reducibility is transitive and reflexive on sets of strings when computable functions compose, a closure property paralleling transitivity properties examined by Emil Post and by Alan Turing in oracle constructions. Many-one reductions are weaker than Turing reducibility but stronger than one-one reducibility variants; their induced equivalence classes form m-degrees analogous to Turing degree structures studied by Alonzo Church and Stephen Kleene. Key results include m-completeness characterizations for recursively enumerable sets (the Halting problem is m-complete among r.e. sets) and NP-completeness under polynomial-time many-one reductions as in the Cook–Levin theorem and Karp's list, connecting to hardness notions used by Leonid Levin and Richard Lipton.

Variants and related reducibilities

Variants include one-one reducibility (1-reducibility) explored by Emil Post and Myhill, polynomial-time many-one reducibility (≤p m) central to Stephen Cook and Richard Karp's NP-completeness, truth-table reducibility and bounded truth-table reducibility used in studies by Marvin Minsky and John Myhill, and Turing reducibility (≤T) from Alan Turing's oracle paradigm. Other related notions comprise log-space reductions influential in work by Jack Edmonds and Neil Immerman, randomized reductions considered by Richard Karp and Leslie Valiant, and parameterized reductions in the parameterized complexity program of Rodney Downey and Michael Fellows.

Applications in computability and complexity

Many-one reductions provide the standard method for proving completeness results: they show that canonical problems like the Halting problem and SAT encapsulate entire classes such as recursively enumerable sets and NP, respectively, a methodology pioneered by Emil Post and extended by Stephen Cook and Richard Karp. In structural analyses they inform degree theory investigated by Gerald Sacks and Barry Cooper, and in cryptographic hardness assumptions they underpin reductions between problems examined by Whitfield Diffie, Martin Hellman, and Ron Rivest. Practical algorithmic lower bounds, complexity class separations conjectures linked to P versus NP and to circuit lower bounds studied by Valiant and Leslie Valiant, frequently use many-one or its resource-bounded variants.

Historical background and development

The conceptual roots trace to recursive function theory of Kurt Gödel, Alonzo Church, and Alan Turing, with explicit reducibility frameworks developed in Emil Post's degree theory and later formalized in complexity contexts by Stephen Cook and Richard Karp in the 1970s. Subsequent expansion involved contributions from Marvin Minsky, Michael Rabin, Stephen Kleene, Leonid Levin, and Yuri Matiyasevich linking to decision problems like Hilbert's tenth problem. Ongoing research continues in connections to structural complexity studied by Neil Immerman and degree theory advanced by Richard Shore and Antonio Montalbán.

Category:Computability theoryCategory:Computational complexity theory