Polynomial Time Reduction

complexity-theory

Definition

Polynomial Time Reduction

A decision problem is said to be polynomial-time reducible to a decision problem , denoted as , if there exists a function that can be computed by an algorithm in polynomial time with respect to the input size . This function must map every instance of problem to an instance of problem such that is a ‘Yes’-instance of if and only if is a ‘Yes’-instance of .

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 , then ” is at least at hard as “.

If , then we can write .

A polynomial time reduction from a decision problem to a decision problem is an algorithm that has the following properties:

1. given an instance of , produces an instance of
2. runs in time polynomial in
3. Answer to YES iff answer to is YES.

Properties

Reflexivity

The polynomial-time reduction relation is reflexive. This means that for any decision problem , it holds that . This is because we can use the identity function as the reduction. The identity function is computable in polynomial time (typically linear time), and it trivially satisfies the condition that is a ‘Yes’-instance of if and only if is a ‘Yes’-instance of .

Transitivity

The polynomial-time reduction relation is transitive. This means that for any three decision problems , , and : If and , then it follows that .

Proof Sketch

Let be the polynomial-time reduction from to (computable in time ) and be the polynomial-time reduction from to (computable in time ).

Define the composition function .

1. Correctness: is a Yes-instance of is a Yes-instance of is a Yes-instance of . Thus, correctly maps instances of to instances of preserving the Yes/No answer.
2. Efficiency: The time to compute is . The size of is polynomial in , say for some polynomial . The time to compute is . The total time for is . Since the composition and sum of polynomials are still polynomials, is computable in polynomial time.

Therefore, . This property allows chaining reductions together to establish relationships between decision problems that are not directly reduced. Along with reflexivity (), transitivity makes 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 and be two decision problems such that . Then the following holds:

1. If , then . If decision problem can be solved efficiently (in polynomial time), then decision problem can also be solved efficiently. To solve , we first apply the polynomial-time reduction to transform an instance of into an instance of , and then use the polynomial time algorithm for to solve . The composition of two polynomial time algorithms results in a polynomial time algorithm overall.
2. If , then . This is the contrapositive of the first point. If decision problem is known to be intractable (i.e., cannot be solved in polynomial time), then decision problem 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 (which is believed to be intractable, i.e., unless ) reduces to decision problem (), then must also be NP-hard (and thus likely intractable).

Examples

Solving by Reduction

Showing Intractability