 Polynomial-time reduction

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$ satisfiesA 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$.

Polynomial-time reduction is a concept in computational complexity theory that describes a way to show that one problem can be transformed into another problem in polynomial time. It serves as a fundamental technique for classifying the difficulty of computational problems and understanding their relationships. ### Key Concepts: 1. **Problem Mapping**: In polynomial-time reduction, we have two problems, let's say Problem A and Problem B. We want to show that Problem A is at most as hard as Problem B.