Hubbry Logo
Many-one reductionMany-one reductionMain
Open search
Many-one reduction
Community hub
Many-one reduction
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Many-one reduction
Many-one reduction
Many-one reduction
View on Wikipedia
from Wikipedia

In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction[1]) is a reduction that converts instances of one decision problem (whether an instance is in ) to another decision problem (whether an instance is in ) using a computable function. The reduced instance is in the language if and only if the initial instance is in its language . Thus if we can decide whether instances are in the language , we can decide whether instances are in the language by applying the reduction and solving for . Thus, reductions can be used to measure the relative computational difficulty of two problems. It is said that reduces to if, in layman's terms is at least as hard to solve as . This means that any algorithm that solves can also be used as part of a (otherwise relatively simple) program that solves .

Many-one reductions are a special case and stronger form of Turing reductions.[1] With many-one reductions, the oracle (that is, our solution for ) can be invoked only once at the end, and the answer cannot be modified. This means that if we want to show that problem can be reduced to problem , we can use our solution for only once in our solution for , unlike in Turing reductions, where we can use our solution for as many times as needed in order to solve the membership problem for the given instance of .

Many-one reductions were first used by Emil Post in a paper published in 1944.[2] Later Norman Shapiro used the same concept in 1956 under the name strong reducibility.[3]

Definitions

[edit]

Formal languages

[edit]

Suppose and are formal languages over the alphabets and , respectively. A many-one reduction from to is a total computable function that has the property that each word is in if and only if is in .

If such a function exists, one says that is many-one reducible or m-reducible to and writes

Subsets of natural numbers

[edit]

Given two sets one says is many-one reducible to and writes

if there exists a total computable function with iff .

If the many-one reduction is injective, one speaks of a one-one reduction and writes .

If the one-one reduction is surjective, one says is recursively isomorphic to and writes[4]p.324

Many-one equivalence

[edit]

If both and , one says is many-one equivalent or m-equivalent to and writes

Many-one completeness (m-completeness)

[edit]

A set is called many-one complete, or simply m-complete, iff is recursively enumerable and every recursively enumerable set is m-reducible to .

Degrees

[edit]

The relation indeed is an equivalence, its equivalence classes are called m-degrees and form a poset with the order induced by .[4]p.257

Some properties of the m-degrees, some of which differ from analogous properties of Turing degrees:[4]pp.555--581

  • There is a well-defined jump operator on the m-degrees.
  • The only m-degree with jump 0m′ is 0m.
  • There are m-degrees where there does not exist where .
  • Every countable linear order with a least element embeds into .
  • The first order theory of is isomorphic to the theory of second-order arithmetic.

There is a characterization of as the unique poset satisfying several explicit properties of its ideals, a similar characterization has eluded the Turing degrees.[4]pp.574--575

Myhill's isomorphism theorem can be stated as follows: "For all sets of natural numbers, ." As a corollary, and have the same equivalence classes.[4]p.325 The equivalences classes of are called the 1-degrees.

Many-one reductions with resource limitations

[edit]

Many-one reductions are often subjected to resource restrictions, for example that the reduction function is computable in polynomial time, logarithmic space, by or circuits, or polylogarithmic projections where each subsequent reduction notion is weaker than the prior; see polynomial-time reduction and log-space reduction for details.

Given decision problems and and an algorithm N that solves instances of , we can use a many-one reduction from to to solve instances of in:

  • the time needed for N plus the time needed for the reduction
  • the maximum of the space needed for N and the space needed for the reduction

We say that a class C of languages (or a subset of the power set of the natural numbers) is closed under many-one reducibility if there exists no reduction from a language outside C to a language in C. If a class is closed under many-one reducibility, then many-one reduction can be used to show that a problem is in C by reducing it to a problem in C. Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, including P, NP, L, NL, co-NP, PSPACE, EXP, and many others. It is known for example that the first four listed are closed up to the very weak reduction notion of polylogarithmic time projections. These classes are not closed under arbitrary many-one reductions, however.

Many-one reductions extended

[edit]

One may also ask about generalized cases of many-one reduction. One such example is e-reduction, where we consider that are recursively enumerable instead of restricting to recursive . The resulting reducibility relation is denoted , and its poset has been studied in a similar vein to that of the Turing degrees. For example, there is a jump set for e-degrees. The e-degrees do admit some properties differing from those of the poset of Turing degrees, e.g. an embedding of the diamond graph into the degrees below .[5]

Properties

[edit]
  • The relations of many-one reducibility and 1-reducibility are transitive and reflexive and thus induce a preorder on the powerset of the natural numbers.
  • if and only if
  • A set is many-one reducible to the halting problem if and only if it is recursively enumerable. This says that with regards to many-one reducibility, the halting problem is the most complicated of all recursively enumerable problems. Thus the halting problem is r.e. complete. Note that it is not the only r.e. complete problem.
  • The specialized halting problem for an individual Turing machine T (i.e., the set of inputs for which T eventually halts) is many-one complete iff T is a universal Turing machine. Emil Post showed that there exist recursively enumerable sets that are neither decidable nor m-complete, and hence that there exist nonuniversal Turing machines whose individual halting problems are nevertheless undecidable.

Karp reductions

[edit]

A polynomial-time many-one reduction from a problem A to a problem B (both of which are usually required to be decision problems) is a polynomial-time algorithm for transforming inputs to problem A into inputs to problem B, such that the transformed problem has the same output as the original problem. An instance x of problem A can be solved by applying this transformation to produce an instance y of problem B, giving y as the input to an algorithm for problem B, and returning its output. Polynomial-time many-one reductions may also be known as polynomial transformations or Karp reductions, named after Richard Karp. A reduction of this type is denoted by or .[6][7]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Many-one reduction

View on Grokipedia
from Grokipedia
In computability theory, a many-one reduction (also known as a mapping reduction) from a decision problem A to a decision problem B is a total computable function f that maps every instance w of A to an instance f(w) of B such that w is a yes-instance of A if and only if f(w) is a yes-instance of B. This reduction preserves the membership status between the two sets of instances, allowing the solvability of A to be inferred from that of B via a single, effective transformation. The concept was first introduced by Emil L. Post in his 1944 address on recursively enumerable sets, where he used it to classify the relative degrees of unsolvability among decision problems for such sets. Post defined many-one reducibility formally as the existence of a recursive function f such that for sets S₁ and S₂ of positive integers, n belongs to S₁ f(n) belongs to S₂, thereby establishing a partial order on the complexity of these problems. He further distinguished it from stricter variants like one-one reducibility (requiring f to be injective) and broader ones like Turing reducibility (allowing adaptive queries to an oracle for B). Many-one reductions play a central role in recursion theory by enabling proofs of relative computability and completeness; for instance, every recursively enumerable set is many-one reducible to the halting problem K, making K the canonical complete set at that level. In complexity theory, they extend to polynomial-time many-one reductions, which underpin the notion of NP-completeness by showing that hard problems like SAT can transform instances of others while preserving solvability in polynomial time. Properties such as closure under composition and the fact that many-one reducibility implies Turing reducibility but not conversely highlight its utility in fine-grained comparisons of computational hardness.

Definitions and Formalisms

General Definition

In , a many-one reduction provides a precise method for comparing the relative computational difficulty of decision problems by establishing a computability-preserving mapping between their instances. Specifically, for two subsets AA and BB of the natural numbers (representing decision problems via membership queries), AA is many-one reducible to BB, denoted A≤mBA \leq_m B, if there exists a total computable function f:N→Nf: \mathbb{N} \to \mathbb{N} such that for every x∈Nx \in \mathbb{N}, x∈Ax \in A if and only if f(x)∈Bf(x) \in B. This means that solving membership in BB allows one to deterministically solve membership in AA by first applying ff to transform the input. The requirement that ff be total and computable distinguishes many-one reductions from other notions, such as those involving partial computable functions, which may not be defined for all inputs and thus fail to provide a uniform transformation across the entire domain. This total computability ensures the reduction is effective and uniform, making it a stricter criterion than Turing reductions, which permit queries that may involve adaptive computations. The concept of many-one reduction was introduced by Emil L. Post in his 1944 paper, where it served as a strengthening of earlier Turing-style reductions to explore the hierarchical structure of degrees of unsolvability among recursively enumerable sets. Post's formulation emphasized its role in classifying decision problems based on their intrinsic complexity. Basic examples illustrate the reduction's simplicity and power. For instance, the halting problem H={⟨M,w⟩∣H = \{ \langle M, w \rangle \mid Turing machine MM halts on input w}}w\} \} reduces to itself via the identity function f(x)=xf(x) = x, which is total computable and preserves membership. A non-trivial example involves reducing the set EE of even natural numbers to the set MM of multiples of 3: define f(n)=3nf(n) = 3n if nn is even and f(n)=3n+1f(n) = 3n + 1 if nn is odd; this ff is total computable, and n∈En \in E if and only if f(n)∈Mf(n) \in M.

Reductions for Formal Languages

In the context of formal languages, a many-one reduction between two languages A,B⊆Σ∗A, B \subseteq \Sigma^*, where Σ\Sigma is a finite , is defined by a total f:Σ∗→Σ∗f: \Sigma^* \to \Sigma^* such that for all strings x∈Σ∗x \in \Sigma^*, x∈Ax \in A f(x)∈Bf(x) \in B. This specializes the general notion of many-one reduction to decision problems over strings, where the computability of ff ensures that membership queries can be effectively transformed while preserving the structure of the languages. Such reductions are foundational in recursion theory for comparing the undecidability of recognition problems. Many-one reductions play a central role in recursion theory by facilitating comparisons between recursively enumerable (r.e.) sets, which correspond to languages accepted by Turing machines. Specifically, if A≤mBA \leq_m B and BB is r.e., then AA is r.e., as the reduction preserves enumerability. To see this, suppose BB is enumerated by a computable procedure that outputs elements b1,b2,…b_1, b_2, \dots. An enumerator for AA can dovetail over all possible strings x∈Σ∗x \in \Sigma^* in order of increasing length and, for each xx, compute f(x)f(x) and simulate the enumeration of BB until either f(x)f(x) appears (in which case xx is output to the enumeration of AA) or a timeout is reached to proceed to the next xx; since ff is computable and if x∈Ax \in A then f(x)∈Bf(x) \in B will eventually be enumerated, this semi-decides membership in AA. A representative example is the many-one reduction from the halting problem, formalized as the language K={⟨p,w⟩∣K = \{ \langle p, w \rangle \mid Turing machine pp halts on input w∈Σ∗}w \in \Sigma^* \}, to the language TOT={e∣TOT = \{ e \mid the ee-th Turing machine is total (halts on all inputs)}. The reduction function ff uses the s-m-n theorem to produce, for each ⟨p,w⟩\langle p, w \rangle, an index e=f(⟨p,w⟩)e = f(\langle p, w \rangle) for a Turing machine ϕe\phi_e whose code embeds the simulation of pp on ww: on any input nn, ϕe(n)\phi_e(n) first simulates pp on ww, and if the simulation halts, outputs 1; the simulation is independent of nn. If ⟨p,w⟩∈K\langle p, w \rangle \in K (simulation halts), then ϕe(n)\phi_e(n) halts and outputs 1 for every nn, so e∈TOTe \in TOT. If ⟨p,w⟩∉K\langle p, w \rangle \notin K (simulation diverges), then the simulation diverges for every nn, so ϕe(n)↑\phi_e(n) \uparrow for all nn, hence e∉TOTe \notin TOT. Thus, ⟨p,w⟩∈K\langle p, w \rangle \in K if and only if f(⟨p,w⟩)∈TOTf(\langle p, w \rangle) \in TOT. Emil Post's theorem on creative sets further highlights the utility of many-one reductions for r.e. languages: every r.e. set is many-one reducible to any creative set, where a creative set C⊆Σ∗C \subseteq \Sigma^* is an r.e. set equipped with a total g:Σ∗→Σ∗g: \Sigma^* \to \Sigma^* such that for any r.e. index ee, if We∩C=∅W_e \cap C = \emptyset then g(e)∈C∖Weg(e) \in C \setminus W_e. This theorem establishes that creative sets, like KK, are many-one complete for the r.e. sets, enabling uniform reductions across all such languages via effective constructions that exploit the creativity condition to "diagonalize" against potential extensions.

Reductions for Subsets of Natural Numbers

In computability theory, many-one reductions for subsets of the natural numbers provide a way to compare the "difficulty" of deciding membership in different sets A,B⊆ωA, B \subseteq \omega. Specifically, A≤mBA \leq_m B if there exists a total recursive function f:ω→ωf: \omega \to \omega such that for all n∈ωn \in \omega, n∈An \in A if and only if f(n)∈Bf(n) \in B. This definition captures a direct, computable translation of instances from AA to BB, preserving decidability properties: if BB is decidable, then so is AA. Such reductions are central to classifying sets within the arithmetic hierarchy, as the preimage under a recursive ff of a Σn0\Sigma_n^0 set is again Σn0\Sigma_n^0, and similarly for Πn0\Pi_n^0. A key application of many-one reductions arises in the study of index sets, which are subsets of ω\omega defined in terms of Gödel numbers or indices of partial recursive functions φe\varphi_e. For instance, index sets like the halting set K={e∈ω∣φe(e)↓}K = \{e \in \omega \mid \varphi_e(e) \downarrow\} serve as complete sets for the recursively enumerable (r.e.) sets under many-one reduction: any r.e. set WeW_e reduces to KK via a computable function that maps inputs to indices of machines simulating the enumeration of WeW_e. Reductions between index sets thus reveal structural properties, such as productivity or creativity, and help delineate the boundaries of the arithmetic hierarchy by showing which index sets are complete at each level (e.g., KK is Σ10\Sigma_1^0-complete). An illustrative example highlighting the non-triviality of many-one reductions involves the complement of the halting set, K‾={e∈ω∣φe(e)↑}\overline{K} = \{e \in \omega \mid \varphi_e(e) \uparrow\}, and KK itself. There is no many-one reduction from K‾\overline{K} to KK, because such an ff would imply K‾=f−1(K)\overline{K} = f^{-1}(K) is r.e. (as preimages of r.e. sets under recursive functions are r.e.), contradicting the fact that K‾\overline{K} is not r.e. while KK is. This incomparability underscores the finer distinctions in many-one degrees compared to Turing degrees, where K≡TK‾K \equiv_T \overline{K}, and demonstrates how many-one reductions fail to capture all computability relations. Unique to reductions over numeric domains are properties tied to the arithmetic structure of ω\omega. For example, many-one reductions can often be constructed to be strictly increasing by incorporating operations like or , such as defining f(n)=2n+g(n)f(n) = 2^n + g(n) where gg is a base reduction, ensuring injectivity and separation of images to avoid overlaps in index constructions. This preservation allows reductions to respect arithmetic closures, facilitating proofs of completeness within arithmetic levels without altering the hierarchical position. The construction of many-one reductions for index sets frequently relies on , which guarantees the existence of fixed points for recursive functionals. This theorem enables self-referential constructions, such as building a reduction ff where the index f(e)f(e) incorporates a simulation of φe\varphi_e while avoiding fixed points that could collapse the reduction (e.g., by parameterizing to ensure f(e)≠ef(e) \neq e for critical ee). Such fixed-point-free techniques are essential for demonstrating separations in many-one degrees among index sets in the arithmetic hierarchy.

Equivalence and Degrees

Many-one Equivalence

In computability theory, two subsets A,B⊆ωA, B \subseteq \omega of the natural numbers are said to be many-one equivalent, denoted A≡mBA \equiv_m B, if AA is many-one reducible to BB and BB is many-one reducible to AA. This means there exist total computable functions f,g:ω→ωf, g: \omega \to \omega such that for all x∈ωx \in \omega, x∈Ax \in A if and only if f(x)∈Bf(x) \in B, and x∈Bx \in B if and only if g(x)∈Ag(x) \in A. The relation ≡m\equiv_m is an equivalence relation on the power set P(ω)\mathcal{P}(\omega). It is reflexive, as the serves as a many-one reduction from any set to itself. It is symmetric by the mutual reducibility in the definition. Transitivity follows from the fact that the composition of total computable functions is total computable: if A≡mBA \equiv_m B via f,gf, g and B≡mCB \equiv_m C via h,kh, k, then A≤mCA \leq_m C via h∘fh \circ f and C≤mAC \leq_m A via g∘kg \circ k. Thus, the equivalence classes under ≡m\equiv_m form a partition of P(ω)\mathcal{P}(\omega). Many-one equivalence preserves key computability properties. In particular, AA is recursively enumerable if and only if BB is recursively enumerable whenever A≡mBA \equiv_m B, because many-one reducibility via a total computable function maps recursively enumerable sets to recursively enumerable sets and vice versa. Similarly, many-one equivalence preserves productivity: if the complement of AA admits a total computable productive function (one that avoids enumerating elements of the complement), then so does the complement of BB. These preservation properties enable the classification of sets into structural categories based on their many-one degrees. A representative example arises with creative sets, which are recursively enumerable sets whose complements are productive. All creative sets are many-one equivalent to one another and to the halting set K={⟨e,x⟩∣ϕe(x)↓}K = \{ \langle e, x \rangle \mid \phi_e(x) \downarrow \}, the canonical complete recursively enumerable set. This follows because a set is creative if and only if it is many-one complete among recursively enumerable sets: every recursively enumerable set (including KK) many-one reduces to it, and it many-one reduces to KK. Historically, Emil Post employed many-one equivalence in his foundational analysis of recursively enumerable sets to delineate structural distinctions, such as between simple sets (recursively enumerable sets whose complements are infinite but contain no infinite recursively enumerable subset) and hypersimple sets (a stricter class where no infinite recursively enumerable subset exists modulo finite differences). Post constructed examples showing simple sets that are not hypersimple, using many-one reducibility to the halting set to establish their incompleteness while preserving recursive enumerability.

Many-one Degrees

The many-one degree of a set AA, denoted d(A)\mathbf{d}(A), is defined as the equivalence class of all sets BB such that B≡mAB \equiv_m A, under the many-one equivalence relation. These degrees are partially ordered by the relation ≤m\leq_m, where d(A)≤md(B)\mathbf{d}(A) \leq_m \mathbf{d}(B) if and only if there exists a many-one reduction from AA to BB. This poset captures the relative computational difficulty of sets with respect to many-one reducibility. The structure of the many-one degrees forms an upper semi-lattice, in which every pair of degrees has a least upper bound given by the join operation. The join d(A)∨d(B)\mathbf{d}(A) \vee \mathbf{d}(B) is the many-one degree of the A⊕B={2x∣x∈A}∪{2y+1∣y∈B}A \oplus B = \{2x \mid x \in A\} \cup \{2y + 1 \mid y \in B\}, which ensures that any common upper bound must encompass the combined information from both sets. This semi-lattice property arises from the fact that many-one reductions preserve the ability to combine sets effectively without introducing unnecessary computational overhead. Significant results in the theory of many-one degrees include the fact that every non-recursive recursively enumerable (r.e.) contains a minimal many-one degree, meaning a degree with no proper non-zero many-one degrees below it. Furthermore, low r.e. sets—those whose Turing jumps are Turing equivalent to the zero jump—can occupy distinct many-one degrees, highlighting the granularity of the structure even among sets of low complexity. These findings underscore the intricate partitioning of degrees within broader Turing classes. A prominent example is the many-one degree of the halting set KK, which serves as the maximal r.e. many-one degree. Every r.e. set is many-one reducible to KK via a computable indexing function that maps elements to their halting computations, establishing KK as an upper bound for all r.e. many-one degrees. Constructions also exist for many-one degrees that lack direct analogs in the Turing degree structure, such as minimal many-one degrees embedded within non-minimal Turing degrees, demonstrating how many-one reducibility can isolate finer levels of unsolvability. In the context of recursion theory, particularly for r.e. sets, the many-one degrees refine the Turing degrees by providing a stricter classification: each Turing degree may contain multiple incomparable many-one degrees, as many-one reducibility imposes additional constraints beyond Turing reducibility. This refinement is evident since any many-one reduction implies a Turing reduction, but the converse does not hold, allowing many-one degrees to distinguish sets that are Turing equivalent.

Completeness and Hardness

Many-one Completeness

In , a set CC is said to be many-one complete (or m-complete) for a class of sets Γ\Gamma if C∈ΓC \in \Gamma and every set B∈ΓB \in \Gamma is many-one reducible to CC, denoted B≤mCB \leq_m C. This notion captures the hardest problems within Γ\Gamma under many-one reductions, meaning that solving CC would allow solving any problem in the class via a computable . A example arises in the class of recursively enumerable (r.e.) sets, where the K={e∣ϕe(e)↓}K = \{ e \mid \phi_e(e) \downarrow \} (with ϕe\phi_e the ee-th partial recursive function) is m-complete. Every r.e. set reduces to KK via many-one reduction, establishing KK as the universal hard instance for r.e. decidability. The completeness of KK for r.e. sets follows from Rice's theorem, which states that any non-trivial index set {e∣We∈Π}\{ e \mid W_e \in \Pi \} (where WeW_e is the domain of ϕe\phi_e and Π\Pi is a non-trivial class of r.e. sets) is many-one reducible to KK. The proof constructs a computable function that maps indices to halting queries, ensuring the reduction preserves membership while leveraging the undecidability of KK. This concept generalizes to higher levels of the , where for each n≥1n \geq 1, there exist m-complete sets for Σn0\Sigma_n^0 and Πn0\Pi_n^0. For instance, the totality problem TOT={e∣ϕe is total}TOT = \{ e \mid \phi_e \text{ is total} \} is m-complete for Π20\Pi_2^0, and similar complete sets exist at each level, allowing reductions from all sets in the class. A distinctive property of m-complete r.e. sets is that every such set is creative: for an m-complete r.e. set CC, there exists a total recursive function ff (a productivity function) such that if We⊆N∖CW_e \subseteq \mathbb{N} \setminus C, then f(e)∈N∖Cf(e) \in \mathbb{N} \setminus C but f(e)∉Wef(e) \notin W_e. This creativity underscores their maximal unsolvability within the r.e. degrees, as originally characterized by Post.

m-Complete Problems

In recursion theory, the halting set K={⟨M,x⟩∣M(x)↓}K = \{ \langle M, x \rangle \mid M(x) \downarrow \}, where MM is a and xx an input, serves as the canonical many-one complete recursively enumerable (r.e.) set. Any r.e. set AA reduces to KK via a computable function ff such that y∈Ay \in A f(y)∈Kf(y) \in K, achieved by encoding the enumeration of AA into simulations by a UU, where f(y)=⟨U,⟨e,y⟩⟩f(y) = \langle U, \langle e, y \rangle \rangle and We=AW_e = A. Other prominent m-complete r.e. sets include creative sets, introduced by Post as r.e. sets whose complements are productive. A set C⊆NC \subseteq \mathbb{N} is creative if it is r.e. and there exists a total recursive function pp such that for every r.e. set WeW_e, if We⊆C‾W_e \subseteq \overline{C} then p(e)∈C‾∖Wep(e) \in \overline{C} \setminus W_e. Every creative set is many-one equivalent to KK, providing an alternative characterization of m-completeness for the r.e. sets. Post's construction of creative sets demonstrates their role in structuring the r.e. degrees below 0′0'. At higher levels of the arithmetical hierarchy, m-complete problems appear in co-r.e. sets and beyond. The complement K‾\overline{K} is many-one complete for the co-r.e. sets (Π⁰₁), as any co-r.e. set reduces to it via negation of the corresponding r.e. reduction to KK. For Σ⁰₂, the infinity problem INF={e∣We is infinite}\mathsf{INF} = \{ e \mid W_e \text{ is infinite} \} is m-complete, capturing sets definable by formulas of the form ∃∞y ∀z φ(e, y, z) where φ is decidable. A representative construction illustrates reductions at these levels: to show the totality problem TOT={e∣∀x φe(x)↓}\mathsf{TOT} = \{ e \mid \forall x \, \varphi_e(x) \downarrow \} (m-complete for Π⁰₂) is undecidable, reduce KK to TOT\mathsf{TOT} by defining, for input ⟨e,x⟩\langle e, x \rangle, a machine index f(e,x)f(e,x) whose computation on input 0 dovetails a simulation of φe(x)\varphi_e(x) while halting immediately on all other inputs; thus, f(e,x)∈TOTf(e,x) \in \mathsf{TOT} if and only if ⟨e,x⟩∈K\langle e, x \rangle \in K. This preserves membership under many-one reduction, leveraging dovetailed simulation to handle the universal quantification in totality. These m-complete problems underpin proofs of undecidability for properties of programs, as formalized by : any non-trivial (property of partial recursive functions holding for some but not all) is many-one complete for the r.e. sets, reducing via modifications to the halting behavior on a fixed input.

Properties and Comparisons

Key Properties

Many-one reductions exhibit several key intrinsic properties that underpin their role in . One fundamental property is monotonicity with respect to set inclusion: if A⊆BA \subseteq B, then A≤mBA \leq_m B. This follows because the serves as a computable many-one reduction from AA to BB, since for any x∈Ax \in A, x∈Ax \in A if and only if x∈Bx \in B (given the inclusion). Another essential property is composition, or transitivity: if A≤mBA \leq_m B via a computable function ff and B≤mCB \leq_m C via a computable function gg, then A≤mCA \leq_m C via the computable composition g∘fg \circ f. This ensures that many-one reducibility forms a on sets, making it a . The composition h=g∘fh = g \circ f satisfies x∈Ax \in A if and only if f(x)∈Bf(x) \in B if and only if g(f(x))=h(x)∈Cg(f(x)) = h(x) \in C, preserving the membership condition. Many-one reductions also preserve certain computability statuses downward. Specifically, if A≤mBA \leq_m B and BB is recursive (decidable), then AA is recursive, as membership in AA can be decided by f(x)f(x) and checking membership in BB. Similarly, if BB is recursively enumerable (r.e.), then AA is r.e., since an enumerator for AA can be obtained by applying ff to the enumerator for BB. For co-r.e. sets (whose complements are r.e.), the preservation holds analogously: if A≤mBA \leq_m B and BB is co-r.e., then AA is co-r.e., because the reduction implies x∉Ax \notin A if and only if f(x)∉Bf(x) \notin B, so the complement of AA reduces to the complement of BB. Finally, many-one reducibility satisfies anti-symmetry in the quotient structure: if A≤mBA \leq_m B and B≤mAB \leq_m A, then AA and BB belong to the same many-one degree, meaning they are many-one equivalent (A≡mBA \equiv_m B). This equivalence implies that AA and BB are indistinguishable in terms of many-one reducibility to other sets, though they may differ up to recursive isomorphism in general.

Comparison to Turing Reductions

Many-one reductions constitute a stricter form of reduction compared to in . A many-one reduction from a set BB to a set AA is witnessed by a total ff such that for every xx, x∈Bx \in B f(x)∈Af(x) \in A, effectively requiring a single oracle query to AA. In contrast, a from BB to AA allows a equipped with an for AA to compute the membership of any xx in BB, potentially through multiple adaptive queries to the oracle. As a result, every many-one reduction induces a (by composing the function ff with a single oracle query), but are strictly more powerful, as they accommodate computations that depend on repeated or conditional oracle consultations. A classic example highlighting this distinction involves the halting set KK (the recursively enumerable set of indices of Turing machines that halt on the empty input) and its complement Kˉ\bar{K}. The set Kˉ\bar{K} is Turing reducible to KK: to decide x∈Kˉx \in \bar{K}, query the oracle for KK on xx and output the negation of the result, which requires only one query but cannot be reformulated as a many-one reduction. If such a computable ff existed with x∈Kˉx \in \bar{K} if and only if f(x)∈Kf(x) \in K, then Kˉ\bar{K} would be recursively enumerable (as the preimage under ff of the r.e. set KK), contradicting the known fact that Kˉ\bar{K} is not r.e. This diagonalization-based argument underscores why many-one reductions fail where Turing reductions succeed. The implications of this extend to degree structures: many-one degrees, formed by equivalence under mutual many-one reducibility, refine the coarser Turing degrees by partitioning them into finer classes, particularly among recursively enumerable (r.e.) sets. Every r.e. set is both many-one and Turing reducible to [K](/page/K)[K](/page/K), establishing [K](/page/K)[K](/page/K) as complete under both notions, but the many-one completeness criterion is stricter, as it requires preserving r.e.-ness more rigidly and yields a denser of incompleteness within the r.e. Turing degrees. Historically, Turing introduced oracle machines in 1939 to model relative and enable Turing for analyzing hierarchies beyond absolute decidability, while Post's 1944 work on recursively enumerable predicates formalized many-one to construct simpler, more tractable degree structures for r.e. sets. For recursive (decidable) sets, however, many-one and s coincide: given recursive AA and BB, a from BB to AA can be simulated by direct of oracle answers, yielding an equivalent many-one reduction via a that encodes the query outcomes.

Variants and Extensions

Resource-Bounded Many-one Reductions

In , resource-bounded many-one reductions extend the classical many-one reduction by restricting the computational resources—such as time or space—used to compute the mapping function between problem instances. A AA is many-one reducible to a BB within a time bound TT, denoted A≤mTBA \leq_m^T B, if there exists a total deterministic that computes a function ff in time O(T(n))O(T(n)) such that for every input xx, x∈Ax \in A f(x)∈Bf(x) \in B. Log-space many-one reductions represent a key special case, where the reducing function ff is computed by a deterministic using O(log⁡n)O(\log n) space on its work tape, with a read-only input tape and a write-only output tape, and ∣f(x)∣≤∣x∣c|f(x)| \leq |x|^c for some constant c>0c > 0. These reductions are polynomially length-increasing and preserve membership in log-space classes. They are essential for defining completeness in nondeterministic log space (NL), where a LL is NL-complete if L∈L \in NL and every in NL reduces to LL via a log-space many-one reduction. The directed st-connectivity problem (PATH), which determines if there exists a directed path from vertex ss to vertex tt in a , is NL-complete under log-space many-one reductions; any nondeterministic log-space machine's configuration graph can be constructed in log space, reducing acceptance to PATH. Log-space many-one reductions compose transitively without resource inflation, as the composition of two such functions remains log-space computable. More generally, time-bounded many-one reductions support the separation and completeness of hierarchies, particularly for superpolynomial or fast-growing time bounds. For complexity classes like DTIME(f(n)f(n)), where ff is time-constructible, a reduction A≤mo(f(n))BA \leq_m^{o(f(n))} B with B∈B \in DTIME(f(n)f(n)) implies A∈A \in DTIME(f(n)f(n)), preserving the hierarchy without collapsing it. In extended hierarchies beyond the elementary functions, such as the fast-growing hierarchy FαF_\alpha indexed by ordinals, time-bounded many-one reductions (using functions from F<αF_{<\alpha}) define complete problems like the of Turing machines bounded by Fα(n)F_\alpha(n) time or the halting of Minsky machines with counters bounded by Fα(∣M∣)F_\alpha(|M|). A representative example is the reduction establishing the completeness of the circuit value problem (CVP) for the class under log-space many-one . CVP asks whether a given CC with input xx evaluates to 1; any language in reduces to CVP in logarithmic space by converting a polynomial-time Turing machine's computation into an equivalent circuit of polynomial size, which can be generated using O(log⁡n)O(\log n) space. Unlike resource-bounded Turing reductions, which allow multiple adaptive queries within a fixed bound, many-one reductions involve a single non-adaptive mapping and thus suffer from potential bound inflation upon composition. Specifically, composing two T(n)T(n)-time many-one reductions yields a reduction computable in time T(T(n))T(T(n)), which can exponentially inflate the bound for superlinear TT and hinder tight preservation of hierarchies in subrecursive classes. This limitation necessitates careful restrictions, such as allowing only a single application of the bounding function in hierarchy definitions to avoid uncontrolled growth.

Extended Many-one Reductions

Truth-table reductions generalize many-one reducibility by allowing a fixed finite number of non-adaptive oracle queries to BB, along with a truth-table that specifies how to compute membership in AA from the answers to those queries. Formally, there is a recursive function that, on input xx, produces a list of query indices y1,…,yky_1, \dots, y_k and a truth-table encoding the computation, such that x∈Ax \in A if and only if the evaluation of the truth-table on the oracle answers for the yiy_i yields acceptance. This form permits multiple non-adaptive queries while directly mapping to a decision output and implies truth-table reducibility. Many-one reducibility is a special case of truth-table reducibility where k=1k=1 and the table simply copies the answer. These extended variants preserve many-one completeness for classes like the recursively enumerable sets, as truth-table mappings maintain the equivalence A≤mBA \leq_m B implying hardness transfer, but they weaken the associated degree structures by allowing finer distinctions in Turing degrees, where more sets become reducible compared to strict many-one. Weak truth-table (WTT) reductions, which bound the number of oracle queries computably from the input, serve as a bounded-use extension of these, further relaxing adaptivity while relating to many-one through the hierarchy where many-one implies WTT but not conversely, thus broadening the scope of reducible sets without error probabilities.

Karp Reductions

Karp reductions, also known as polynomial-time many-one reductions, are a specific type of many-one reduction where the reducing function ff is computable in polynomial time. Formally, for languages A,B⊆{0,1}∗A, B \subseteq \{0,1\}^*, A≤pBA \leq_p B if there exists a polynomial-time f:{0,1}∗→{0,1}∗f: \{0,1\}^* \to \{0,1\}^* such that for all x∈{0,1}∗x \in \{0,1\}^*, x∈Ax \in A f(x)∈Bf(x) \in B. This ensures that the reduction preserves membership in a computationally efficient manner, making it suitable for establishing hardness within polynomial-time complexity classes. Introduced by Richard M. Karp in 1972, these reductions played a pivotal role in demonstrating the of 21 combinatorial problems, including classics like the traveling salesman problem and . Karp built upon Stephen Cook's 1971 work, which established the of SAT using a , by showing that many-one reductions suffice for a broad class of problems in NP. A key theorem in this context is that SAT is complete for NP under polynomial-time many-one reductions, enabling the transfer of hardness across the class without relying on more powerful s. A representative example of a Karp reduction is the polynomial-time transformation from 3-SAT to . Given a 3-CNF formula ϕ\phi with mm clauses, construct a graph GG with a vertex for each literal in the clauses and edges connecting literals from the same clause or complementary literals across clauses; set k=2mk = 2m. Then, ϕ\phi is satisfiable if and only if GG has a of size at most kk, with the reduction computable in O(m)O(m) time. This encoding ensures that selecting vertices corresponds to choosing truth assignments that cover all clause implications. The implications of Karp reductions are profound for complexity theory: NP is closed under these , meaning if B∈NPB \in \mathrm{NP} and A≤pBA \leq_p B, then A∈NPA \in \mathrm{NP}. Consequently, if any NP-complete problem (under Karp reductions) is in P, then P = NP, as hardness would propagate to all of NP. In modern contexts, Karp reductions extend to , where fixed-parameter tractable (FPT) reductions function as bounded many-one reductions computable in f(k)⋅nO(1)f(k) \cdot n^{O(1)} time, preserving membership in FPT and enabling kernelization techniques for problems like parameterized by solution size.

References

  1. https://courses.grainger.illinois.edu/cs373/fa2010/lectures/notes17.pdf
  2. https://www.andrew.cmu.edu/user/kk3n/recursionclass/8reduction.html
  3. https://www.ams.org/bull/1944-50-05/S0002-9904-1944-08111-1/S0002-9904-1944-08111-1.pdf
  4. https://www.andrew.cmu.edu/user/kk3n/complearn/chapter7.pdf
  5. https://courses.grainger.illinois.edu/cs474/fa2021/reductions.pdf
  6. https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf
  7. https://www.cs.cornell.edu/courses/cs4820/2013sp/Handouts/reductions.pdf
  8. https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-50/issue-5/Recursively-enumerable-sets-of-positive-integers-and-their-decision-problems/bams/1183505800.full
  9. https://plato.stanford.edu/entries/recursive-functions/
  10. https://www.comp.nus.edu.sg/~fstephan/recursiontheory-pstopdf.pdf
  11. https://people.math.wisc.edu/~awmille1/old/m773-07/cmpthy.pdf
  12. https://www.jstor.org/stable/2274914
  13. https://builds.openlogicproject.org/content/computability/computability-theory/computability-theory.pdf
  14. https://link.springer.com/chapter/10.1007/978-3-540-69407-6_53
  15. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/D97E5826FBE3D9D1895DD1D93651CAF5/S0008414X00046708a.pdf/initial_segments_of_manyone_degrees.pdf
  16. https://link.springer.com/content/pdf/10.1007/BF02219743.pdf
  17. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/6C35ECCBCEDF77717315150B1D8F5BF4/S0022481200092197a.pdf/turing_degrees_and_manyone_degrees_of_maximal_sets.pdf
  18. https://www.cis.upenn.edu/~jean/old511/html/cis51108sl11.pdf
  19. https://www.cs.toronto.edu/~sacook/csc438h/notes/page71.pdf
  20. https://mathweb.ucsd.edu/~sbuss/CourseWeb/Math260_2012WS/Apr16_Chen.pdf
  21. https://www.ams.org/journals/tran/1953-074-02/S0002-9947-1953-0053041-6/S0002-9947-1953-0053041-6.pdf
  22. https://math.colorado.edu/~mayr/teaching/math6010spring21/class18.pdf
  23. https://www.cs.cmu.edu/~cdm/resources/60-arith-hier.pdf
  24. https://math.colorado.edu/~mayr/teaching/math6010spring21/class20.pdf
  25. https://sites.ualberta.ca/~francisp/Phil428.526/UrquhartPost.pdf
  26. http://www.piergiorgioodifreddi.it/wp-content/uploads/2010/10/CRT1.pdf
  27. https://math.colorado.edu/~mayr/teaching/math6010spring21/class24.pdf
  28. https://mathoverflow.net/questions/238220/turing-and-many-one-reductions-in-computability-versus-complexity
  29. https://people.math.ethz.ch/~halorenz/4students/Literatur/TuringOrdinalLogic.pdf
  30. https://people.irisa.fr/Nicolas.Markey/PDF/Papers/toct8(1)-Sch.pdf
  31. https://theory.cs.princeton.edu/complexity/spacechap.pdf
  32. https://www.cs.cornell.edu/courses/cs6820/2022fa/Handouts/CVP.pdf
  33. https://homepages.ecs.vuw.ac.nz/~downey/publications/WttBookFinal.pdf
  34. https://projecteuclid.org/journals/notre-dame-journal-of-formal-logic/volume-32/issue-2/Bounds-in-weak-truth-table-reducibility/10.1305/ndjfl/1093635747.full
  35. https://theory.cs.princeton.edu/complexity/NPchap.pdf
  36. https://www.cs.purdue.edu/homes/hosking/197/canon/karp.pdf
  37. https://www.cs.toronto.edu/~sacook/homepage/1971.pdf
  38. https://link.springer.com/book/10.1007/978-1-4612-0515-9
Add your contribution
Related Hubs
User Avatar
No comments yet.