Linked from

The 15 pages that link to Many-one reduction, each with the reason it gives.

• Computability theoryRelated: Reductions compare problem difficulty without requiring direct solutions.

• Decision problemRelated: Reductions transfer decidability results between decision problems.

• Rice's theoremRelated: A program and input are encoded into a new program whose property reveals whether the original halts.

• Polynomial-time reductionBroader topic: It is the standard instance-by-instance form of polynomial-time reduction.

• DecidabilityRelated: Reductions transfer undecidability from a known hard problem to a target problem.

• NP-hardnessBroader topic: Polynomial-time many-one reductions are the standard basis for many NP-hardness claims.

• Undecidable problemRelated: A reduction transfers undecidability from a known problem to a new one.

• Arithmetical hierarchyRelated: Completeness under these reductions identifies sets as representative hardest examples at a level.

• Oracle Turing machineCompared with: It uses a single transformed instance rather than adaptive oracle queries.

• Computable setRelated: Reductions compare the difficulty of deciding computable and noncomputable sets.

• Theoretical computer scienceRelated: Reductions compare problem difficulty and transfer hardness results.

• Post's theoremRelated: Reductions compare the completeness of jump sets and hierarchy levels.

• S-m-n theoremRelated: The theorem helps build computable maps between indices when reducing program properties.

• Turing degreeCompared with: It is a stricter reducibility than Turing reducibility and yields finer comparisons.

• Trakhtenbrot's theoremRelated: It transfers undecidability from the halting problem to finite satisfiability.