---
title: "Polynomial time reduction"
subject: "Theory of Computation"
chapter: 6
key: "semester_3/theory_of_computation:polynomial-time-reduction"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/polynomial-time-reduction
site: BCT Engineering
---

# Polynomial time reduction

Theory of Computation · Chapter 6: Computational Complexity

- Asked in: 2073 Chaitra
- Video: [What is a polynomial-time reduction? (NP-Hard + NP-complete)](https://www.youtube.com/watch?v=O7pq43hIE_0) — Easy Theory
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/polynomial-time-reduction
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-6

## Question

Define polynomial time reduction.

## Short answer

Polynomial-time reduction (≤p) means a language A is reducible to B if a polynomial-time computable function f maps instances w such that w∈A iff f(w)∈B. It preserves yes/no answers. Used to show NP-hardness: if A is NP-hard and A ≤p B, then B is NP-hard. Transitivity allows chaining reductions.

## Answer

#### Definition
A language (decision problem) A is **polynomial-time reducible** to a language B, written **A ≤p B**, if there is a function f : Σ* → Σ* such that
1. f is computable by a deterministic TM in **polynomial time**, and
2. for every string w: **w ∈ A if and only if f(w) ∈ B**.

The function f is called a **polynomial-time (many-one or Karp) reduction**. It transforms every instance of A into an instance of B with the same yes/no answer.

```text
   instance w of A ──f (poly time)──► f(w), an instance of B
        yes/no for w  ==  yes/no for f(w)
```

#### Consequences
- If A ≤p B and B ∈ P, then A ∈ P (run f, then the polynomial algorithm for B; a polynomial of a polynomial is a polynomial).
- If A ≤p B and A is NP-hard (or NP-complete), then B is NP-hard. This is how NP-completeness of new problems is shown: reduce a known NP-complete problem to them.
- ≤p is transitive: A ≤p B and B ≤p C give A ≤p C.

#### Example: 3-SAT ≤p CLIQUE
Given a 3-CNF formula φ with k clauses, build a graph G: one vertex for each literal occurrence in each clause; join two vertices by an edge unless they are in the same clause or are contradictory literals (x and ¬x). Then φ is satisfiable if and only if G has a clique of size k. The construction takes polynomial time, so 3-SAT ≤p CLIQUE, and CLIQUE is NP-hard.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What two conditions define A ≤p B?
   A. A function f computable in polynomial time, with w in A if and only if f(w) in B
   B. A function f computable in exponential time, with w in A implies f(w) in B
   C. A function f computable in polynomial time, with w in A or f(w) in B
   D. A function f that maps B to A in polynomial time
   Answer: A. f must be polynomial-time computable and preserve the yes/no answer in both directions (if and only if). (Key point: Definition)

2. If A ≤p B and B is in P, what follows?
   A. A is NP-hard
   B. A is in P, since a polynomial of a polynomial is polynomial
   C. Nothing can be concluded about A
   D. B is in NP-complete
   Answer: B. Run f in polynomial time then the polynomial algorithm for B; the total is still polynomial. (Key point: Reduction to a problem in P)

3. How is a new problem B shown to be NP-hard using reductions?
   A. Reduce B to a known NP-complete problem
   B. Show B is in P
   C. Reduce a known NP-complete (or NP-hard) problem A to B, i.e. A ≤p B
   D. Show B is undecidable
   Answer: C. If A is NP-hard and A ≤p B, then B is at least as hard, so B is NP-hard. Reducing in the other direction proves nothing about hardness. (Key point: Proving NP-hardness)

4. In the reduction 3-SAT ≤p CLIQUE for a formula with k clauses, how is the graph built and what is claimed?
   A. One vertex per variable; edges join variables in the same clause; satisfiable iff a clique of size 3 exists
   B. One vertex per literal occurrence; edges join vertices unless in the same clause or contradictory; satisfiable iff a clique of size k exists
   C. One vertex per clause; edges between all clauses; satisfiable iff a clique of size k exists
   D. One vertex per literal occurrence; edges join vertices in the same clause; satisfiable iff a clique of size 2 exists
   Answer: B. A clique of size k picks one non-contradicting literal from each clause, which gives a satisfying assignment. (Key point: 3-SAT to CLIQUE construction)

## Related in other subjects

- [Reservoir routing through spillway, 6-hr inflow](https://www.bctengineer.com/question.md?key=semester_5%2Fengineering_hydrology%3Areservoir-routing-spillway-6hr) — Engineering Hydrology, chapter 7
- [Muskingum routing, K=36 hr, x=0.15](https://www.bctengineer.com/question.md?key=semester_5%2Fengineering_hydrology%3Amuskingum-k36-x0-15) — Engineering Hydrology, chapter 7