Polynomial-time counting reduction

A polynomial-time counting reduction is usually used to transform instances of a known-hard problem ${\displaystyle X}$ into instances of another problem ${\displaystyle Y}$ that is to be proven hard. It consists of two functions ${\displaystyle f}$ and ${\displaystyle g}$, both of which must be computable in polynomial time. The function ${\displaystyle f}$ transforms inputs for ${\displaystyle X}$ into inputs for ${\displaystyle Y}$, and the function ${\displaystyle g}$ transforms outputs for ${\displaystyle Y}$ into outputs for ${\displaystyle X}$.^[1][2]

These two functions must preserve the correctness of the output. That is, suppose that one transforms an input ${\displaystyle x}$ for problem ${\displaystyle X}$ to an input ${\displaystyle y=f(x)}$ for problem ${\displaystyle Y}$, and then one solves ${\displaystyle y}$ to produce an output ${\displaystyle z}$. It must be the case that the transformed output ${\displaystyle g(z)}$ is a correct output for the original input ${\displaystyle x}$. That is, if the input–output relations of ${\displaystyle X}$ and ${\displaystyle Y}$ are expressed as functions, then their function composition must obey the identity ${\displaystyle X=g\circ Y\circ f}$. Alternatively, expressed in terms of algorithms, one possible algorithm for solving ${\displaystyle X}$ would be to apply ${\displaystyle f}$ to transform the problem into an instance of ${\displaystyle Y}$, solve that instance, and then apply ${\displaystyle g}$ to transform the output of ${\displaystyle Y}$ into the correct answer for ${\displaystyle X}$.^[1][2]