Difficulty: Intermediate to Advanced | Prerequisites: P, NP, NP-hardness definitions; Turing reductions; basic proof techniques (proof by contradiction, counterexample).
Polynomial-time mapping reductions (PTMRs, also called Karp reductions) are the standard tool for proving NP-hardness. A PTMR from A to B transforms any instance of A into an instance of B in polynomial time, preserving yes/no answers. This is more restrictive than a Turing reduction, which can query an oracle multiple times. Understanding PTMRs, their relationship to Turing reductions, and their properties (especially transitivity) is essential for every NP-completeness proof in the course.
Every Karp reduction is also a Turing reduction, but the reverse is false. PTMRs are transitive (if A reduces to B and B reduces to C, then A reduces to C, via function composition). If P = NP, then every non-trivial language is NP-hard, but the trivial languages (the empty set and the set of all strings) are never NP-hard.
Polynomial-time mapping reduction (PTMR / Karp reduction), A <=p B
An efficiently computable function f such that x is in A if and only if f(x) is in B. One call to f, one transformation, done. Think of it as: a translator that converts problem A into problem B, preserving the answer.
Turing reduction, A <=T B
A polynomial-time algorithm for A that may use an oracle for B as a subroutine, calling it as many times as needed. Think of it as: solving A by asking the B-oracle questions, possibly many.
Trivial languages
The two extreme languages: the empty set (contains nothing) and the set of all strings over the alphabet (contains everything). These are not NP-hard, regardless of whether P = NP.
Non-trivial language
Any language that is neither the empty set nor the set of all strings. It contains at least one "yes" instance and at least one "no" instance.
Transitivity of reductions
If A <=p B and B <=p C, then A <=p C. The reduction function is the composition g(f(x)), and composition of polynomials is polynomial.
Suppose f is the poly-time mapping reduction from A to B, so x is in A iff f(x) is in B.
Construct a Turing reduction: given oracle D_B for B, define M_A(x) = D_B(f(x)).
M_A computes f(x) in poly time, queries the oracle once, and outputs the result.
Correctness: x is in A iff f(x) is in B iff D_B(f(x)) accepts iff M_A(x) accepts.
Intuition: a mapping reduction is a special case of a Turing reduction that makes exactly one oracle query and outputs the oracle's answer directly.
Counterexample using trivial languages: let A be any non-empty decidable language (e.g. 3SAT), and let B = the set of all strings.
A <=T B holds because A is decidable (you can decide A without even using the oracle).
A <=p B fails: a PTMR needs x not in A to map to some y not in B. But B is the set of all strings, so no such y exists.
Similarly, A <=T the empty set holds, but A <=p the empty set fails because there is no y in the empty set to map "yes" instances to.
Alternative approach (using the time hierarchy theorem): there exist decidable languages not in P. Such a language L satisfies L <=T L' for any decidable L', but L is not poly-time reducible to any language in P.
Given: f is a PTMR from A to B (runs in time O(|x|^c), output length O(|x|^c)).
Given: g is a PTMR from B to C (runs in time O(|y|^{c'})).
Define h(x) = g(f(x)). Then x is in A iff f(x) is in B iff g(f(x)) is in C.
Runtime of h: O(|x|^c) for f, plus O(|f(x)|^{c'}) = O(|x|^{c * c'}) for g. Total: O(|x|^{max(c, c*c')}), which is polynomial.
This is why NP-hardness chains work: if you know 3SAT <=p CLIQUE and CLIQUE <=p your problem, then 3SAT <=p your problem.
Let L* be any non-trivial language, so there exist strings a in L* and b not in L*.
Let L be any NP language. Under P = NP, L is in P, so it has an efficient decider D.
Construct PTMR f: if D(x) accepts, return a; if D(x) rejects, return b.
f is efficient (D is), and x is in L iff f(x) = a iff f(x) is in L*.
Non-triviality is essential: if L* were the empty set, there would be no a to return. If L* were the set of all strings, there would be no b to return.
Students often assume Turing reductions and mapping reductions are equivalent. They are not. Every PTMR is a Turing reduction, but not vice versa.
A common mistake in the transitivity proof is forgetting to show that the composition h = g(f(x)) runs in polynomial time. You must bound the output length of f to bound the runtime of g on that output.
Students sometimes forget that trivial languages break mapping reductions. You cannot map out of the empty set or into the complement of the set of all strings, because the needed target strings do not exist.
"Prove or disprove" questions about the relationship between <=p and <=T appear frequently. Keep the trivial-language counterexample ready.
The transitivity proof is a standard exam question. Practise writing the runtime bound for the composition.
The P = NP consequence (every non-trivial language becomes NP-hard) tests whether you understand why non-triviality is needed. Expect to be asked where in the proof you rely on it.
True or False: A <=p B implies A <=T B. (True.)
True or False: A <=T B implies A <=p B. (False.)
Fill in the blank: PTMRs are transitive because the ______ of two polynomial-time functions is polynomial-time. (composition)
True or False: If P = NP, the empty language is NP-hard. (False, trivial languages are never NP-hard.)
Q: Prove that if A <=p B, then A <=T B.
A: Let f be the PTMR, so x is in A iff f(x) is in B. Given oracle D_B for B, define M_A(x) = D_B(f(x)). M_A halts on all inputs, computes f in poly time, and x is in A iff f(x) is in B iff D_B(f(x)) accepts.
Q: Prove that PTMRs are transitive.
A: Given f: A <=p B running in O(|x|^c) and g: B <=p C running in O(|y|^{c'}), define h(x) = g(f(x)). Correctness: x is in A iff f(x) is in B iff g(f(x)) is in C. Runtime: O(|x|^c + |x|^{cc'}) = O(|x|^{max(c, cc')}), polynomial.
Q: Why are trivial languages not NP-hard, even if P = NP?
A: A PTMR requires x in L to map to some y in L*, and x not in L to map to some y not in L*. If L* is the set of all strings, no y outside L* exists. If L* is empty, no y inside L* exists. So no PTMR can be constructed.
Transitivity of PTMRs is the engine behind every NP-completeness proof: you reduce from a known NP-hard problem (like 3SAT) to your target, chaining through the existing web of reductions. This connects directly to the Dominating Set and Subgraph Isomorphism problems in the next set of notes, where you build specific PTMRs from 3SAT and CLIQUE.
Karp reduction, mapping reduction, PTMR, polynomial-time reduction, Turing reduction, Cook reduction, transitivity, function composition, trivial language, non-trivial language, P equals NP, NP-hardness proof, oracle, EECS 376, Handout 6