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.

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

• 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.

• 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.

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