Polynomial-time reduction

Remarks

Example: let $A$ be the set of encodings of pairs $(G, k)$ where the graph $G$ has an independent set of size $k$. Let $B$ be the set of pairs $(G, k)$ where $G$ has a clique of size $k$. The map $(G, k) \mapsto (\overline{G}, k)$, with $\overline{G}$ the complement graph, is computable in polynomial time. A set of vertices is independent in $G$ exactly when it is a clique in $\overline{G}$, so clause 2 holds and $A \le_p B$.

Non-example: the map that sends $(G, k)$ to a fixed yes-instance of $B$ when $A$ holds, and to a fixed no-instance otherwise, satisfies clause 2. No polynomial-time algorithm is known to compute it, so it is not known to satisfy clause 1.

Such reductions are also called Karp reductions or polynomial-time many-one reductions. The relation $\le_p$ is reflexive and transitive. If $A \le_p B$ and $B \in$ P, then $A \in \mathrm{P}$. A Cook reduction is the weaker notion where $A$ is decided in polynomial time by a machine that may ask many questions about $B$.