Polynomial-time reduction

A polynomial-time reduction transforms instances of one decision problem into instances of another in polynomial time while preserving whether the answer is yes or no.

Many-one reduction: A reduction maps each instance of one problem to a single instance of another, preserving yes-or-no answers. It is the standard instance-by-instance form of polynomial-time reduction.
NP-hardness: A problem is NP-hard if every problem in NP reduces to it under a specified reduction notion. A reduction from an NP-hard problem transfers its hardness to the target.
Log-space reduction: A reduction computable with logarithmic workspace, typically using polynomial time. It restricts transformation space more tightly than polynomial-time reduction.
Computational complexity theory: The study of the resources required to solve computational problems. Polynomial-time reductions compare problem difficulty within this framework.
Turing reduction: A reduction solves one problem using an oracle for another, potentially making multiple adaptive queries. It allows more interaction than a single answer-preserving instance transformation.
NP-completeness: A decision problem is NP-complete if it belongs to NP and is NP-hard. Polynomial-time reductions are the standard tool for proving NP-hardness.
Polynomial-time Turing reduction: A reduction that solves one problem in polynomial time while querying an oracle for another. Unlike a many-one reduction, it may make several queries and use their answers adaptively.
Input size: The length of an encoded input, used to measure an algorithm's resource requirements. Polynomial time is measured against the length of the encoded instance.
Polynomial-time computable function: A function is polynomial-time computable if a deterministic algorithm outputs its value in time bounded by a polynomial in input length. The transformation must meet this resource bound.
Cook–Levin theorem: The theorem that Boolean satisfiability is NP-complete under polynomial-time many-one reductions. It supplies the foundational starting point for many NP-completeness proofs.

Linked from 16 pages