Polynomial Time Reduction

complexity-theory

Definition

Polynomial Time Reduction

A decision problem $A$ is said to be polynomial-time reducible to a decision problem $B$, denoted as $A{\le }_{P}B$, if there exists a function $f$ that can be computed by an algorithm in polynomial time with respect to the input size $|x|$. This function $f$ must map every instance $x$ of problem $A$ to an instance $f(x)$ of problem $B$ such that $x$ is a ‘Yes’-instance of $A$ if and only if $f(x)$ is a ‘Yes’-instance of $B$.

Essentially, a polynomial-time reduction provides an efficient way to transform instances of one decision problem into instances of another while preserving the answer to the decision question. This concept is crucial for classifying problems based on their relative difficulty, particularly in the context of NP-completeness.

If $X{\le }_{P}Y$, then ”$Y$ is at least at hard as $X$“.

Properties

Reflexivity

The polynomial-time reduction relation ${\le }_P$ is reflexive. This means that for any decision problem $A$, it holds that $A{\le }_{P}A$. This is because we can use the identity function $f(x)=x$ as the reduction. The identity function is computable in polynomial time (typically linear time), and it trivially satisfies the condition that $x$ is a ‘Yes’-instance of $A$ if and only if $f(x)=x$ is a ‘Yes’-instance of $A$.

Transitivity

The polynomial-time reduction relation ${\le }_P$ is transitive. This means that for any three decision problems $A$, $B$, and $C$: If $A{\le }_{P}B$ and $B{\le }_{P}C$, then it follows that $A{\le }_{P}C$.

Proof Sketch

Let $f$ be the polynomial-time reduction from $A$ to $B$ (computable in time $p_f(|x|)$) and $g$ be the polynomial-time reduction from $B$ to $C$ (computable in time $p_g(|y|)$).

Define the composition function $h(x)=g(f(x))$.

1. Correctness: $x$ is a Yes-instance of $A⟺f(x)$ is a Yes-instance of $B⟺g(f(x))$ is a Yes-instance of $C$. Thus, $h(x)$ correctly maps instances of $A$ to instances of $C$ preserving the Yes/No answer.
2. Efficiency: The time to compute $f(x)$ is $p_f(|x|)$. The size of $f(x)$ is polynomial in $|x|$, say $|f(x)|\le q(|x|)$ for some polynomial $q$. The time to compute $g(f(x))$ is $p_g(|f(x)|)\le p_g(q(|x|))$. The total time for $h(x)$ is $p_f(|x|)+p_g(q(|x|))$. Since the composition and sum of polynomials are still polynomials, $h(x)$ is computable in polynomial time.

Therefore, $A{\le }_{P}C$. This property allows chaining reductions together to establish relationships between decision problems that are not directly reduced. Along with reflexivity ($A{\le }_{P}A$), transitivity makes ${\le }_P$ a preorder on the set of decision problems.

Tractability

Polynomial-time reductions provide a way to formally relate the difficulty of decision problems, specifically concerning whether they belong to the complexity class P (the class of tractable problems).

Let $A$ and $B$ be two decision problems such that $A{\le }_{P}B$. Then the following holds:

1. If $B\in P$, then $A\in P$. If decision problem $B$ can be solved efficiently (in polynomial time), then decision problem $A$ can also be solved efficiently. To solve $A$, we first apply the polynomial-time reduction $f$ to transform an instance $x$ of $A$ into an instance $f(x)$ of $B$, and then use the polynomial time algorithm for $B$ to solve $f(x)$. The composition of two polynomial time algorithms results in a polynomial time algorithm overall.
2. If $A\notin P$, then $B\notin P$. This is the contrapositive of the first point. If decision problem $A$ is known to be intractable (i.e., cannot be solved in polynomial time), then decision problem $B$ must also be intractable. This second implication is fundamental for proving that decision problems are computationally hard. Specifically, it’s the cornerstone of NP-hardness proofs. If we can show that a known NP-hard problem $A$ (which is believed to be intractable, i.e., $A\notin P$ unless $P=NP$) reduces to decision problem $B$ ($A{\le }_{P}B$), then $B$ must also be NP-hard (and thus likely intractable).

Examples

Solving by Reduction

Showing Intractability