= Polynomial-time reduction
{wiki}
A <polynomial-time reduction> uses a solver for one <computational problem> to solve another with polynomial overhead, while preserving the required answer. Efficiently transforming data alone is insufficient: the transformation must come with a correctness argument connecting the two tasks.
For a <polynomial-time many-one reduction> between <decision problems> $A,B$, one <function> $r$ satisfies
$$
x\in A\quad\Longleftrightarrow\quad r(x)\in B.
$$
A <polynomial-time Turing reduction> instead permits adaptively chosen queries to a solver for $B$. Writing the queries and processing their answers count toward the reduction's resource bound. These are different reduction conventions and should be named explicitly.
If $B$ has a <polynomial-time algorithm>, either such reduction supplies one for $A$: query lengths and the total number of queries are polynomially bounded, so replacing each solver call preserves a polynomial total <running time>. Conversely, a reduction from a hard $A$ helps establish a lower bound on $B$.
Back to article page
