Linked from

The 16 pages that link to Polynomial-time reduction, each with the reason it gives.

• P versus NP problemRelated: Reductions compare problem difficulty and transfer efficient algorithms.

• Boolean satisfiability problemRelated: Reductions transfer SAT's hardness to other decision problems.

• Cook–Levin theoremRelated: The construction must encode each input without exceeding polynomial time or formula size.

• Polynomial degreeRelated: Here “polynomial” describes runtime growth, not the degree of an algebraic expression.

• Polynomial timeRelated: Such reductions compare problem difficulty without exceeding polynomial overhead.

• Leonid LevinRelated: Reductions transfer hardness from known difficult problems to new ones.

• Stephen CookRelated: Cook used reductions to show that every NP problem can be represented by satisfiability.

• Hamiltonian pathRelated: Reductions establish the hardness of Hamiltonian path by transferring difficulty from other problems.

• Nondeterministic Turing machineRelated: Reductions compare the difficulty of problems characterized through nondeterministic computation.

• Hartmanis–Stearns conjectureRelated: Reductions compare problem difficulty and transfer consequences of a proof about P and NP.

• PCP theoremRelated: Reductions carry PCP-based hardness from verifier constructions to concrete problems.

• Richard M. KarpRelated: Karp used these transformations to transfer NP-hardness from one problem to another.