Lecture 7: P vs NP and Karp's Reducibility

Administrative Updates

• Quiz #1 is scheduled for one week from today (February 25, 2026) and will be administered on Brightspace.

• Review Session: Monday, February 23rd in the virtual classroom will serve as a review session for Quiz #1. This review will cover all material from previous lectures.

• No Virtual Classroom on the Wednesday following the review.

• Preparation for Review: Students should review all lecture notes and prepare specific questions for Monday. The instructor prefers that students come prepared with questions rather than starting fresh during the review session.

• Quiz Scope: Quiz #1 will focus primarily on the first lecture’s material covering reductions and the foundational concepts discussed today. The notation explanations will be included in supplementary notes below the main lecture material.

• Future Work: After Quiz #1, the course will spend one to two weeks covering Karp’s 21 NP-complete problems. Students are encouraged to bring Karp’s paper to future lectures.

• Attendance: Students who did not stay for the entire session should text the word “present” by end of class.

Reductions

For the next two weeks of lectures, bring Karp’s paper with you. We will be discussing the relevant (application oriented) portions.

The first paragraph here was discussed at end of last lecture and included here for providing context to this tab.

P and NP: Definitions and Distinction

P (Polynomial): All algorithms that take a polynomial amount of time to run on a standard (deterministic) computer. These are algorithms we can practically solve.

NP (Nondeterministic Polynomial): All algorithms that would take a polynomial amount of time to run on a nondeterministic machine. The nondeterministic machine can “guess” a solution, and we need only verify it in polynomial time.

The Complexity Distinction (Edmonds): Polynomial algorithms are “easy” (tractable); exponential algorithms are “hard” (intractable). This distinction inspired Cook and Karp’s work on hard problems.

The first problem that was shown to be NP-hard was Satisfiability, find a sequence of true/false (ie 0/1) values that will cause a Boolean Predicate to be True.

Cook (1971) proved this and shows that ALL possible NP-hard problems must “reduce” to Satisfiability.

Cook defines reduction in one direction, from your Problem/Algorithm to Satisfiability.

Karp argued that to show equivalent hardness, one must reduce two problems to each other (bidirectional reduction).

Yet, in Karp’s paper he only shows one direction: namely, Satisfiability reduces to other problems (and continues for a total of 20 other problems). This apparent paradox is readily solved when you realize that COOK already SHOWED the other direction, so Karp only needed to show the second direction. In terms of definitions, KARP held that two problems must reduce to each other to prove equivalent hardness, but Cook’s prior proof of the reverse direction made Karp’s unidirectional proof sufficient.

A third definition of reduction was given by Levin, inspired by the fact that Nondeterminism is relativized computing (defined above). So, Levin said that reduction is about seeking an external piece of information or source that will help you solve the second problem given a first problem. The hardness is then how hard (complexity) is the cost of obtaining that missing piece of information. Although we do not entertain Levin’s reduction definition when discussing the KARP-21, There is an interesting case discussed at the end of these notes below which will benefit from Levin’s perspective.

The above discussion was presented at the end of the last lecture. It is included here so we have a context for today’s and subsequent classes. In the literature, if we write

(see below for why this notation was used)

this notation is read as “reduces to” , but the actual meaning (in Karp’s paper) is the following:

1. B is known to be hard and A is unknown cf. last lecture’s notes, line 91

2. A solves B’s problem (that is consistent with the both cases above)

3. B is the parent considered in the reduction tree cf. Karp, p. 96, Reduction Tree Summary

4. A is the child (of B) considered in the reduction tree

5. The root of the entire tree is SATisfiability Karp#1

6. In this context, it is the CHILD (A) that solves the PARENT’s (B) problem. cf. last lecture’s notes, line 110

7. B reduces TO cf. last lecture’s notes, line 106

8. A reduces FROM B

9. Conclusion: is as hard as . NOTE: Remember that for Karp, this only based on the fact that the other direction was already provided by Cook’s analysis.

Another notation for reduction, consistent with our entire discussion, is the infinity symbol or the less-than-or-equal symbol. Think of it as an 8 lying sideways and the right most tip then cut off.

To emphasize the need to transform between the NP problems within a reasonable amount of time, many put a “p” at the foot of the "" symbol, giving us .

Let us take a pair of problems from Karp’s Reduction Tree Summary (Karp, p. 96) and derive these nine pieces of information as they apply to a pair of problems. For example, Chromatic Number (KARP#12) reduces to Clique Cover (KARP#13).

Problem #1 (): Chromatic Number (KARP#12)

Problem #2 (): Clique Cover (KARP#13)

Then, at the point of the tree where Chromatic Number connects to Clique Cover:

1. Chromatic Number is known to be hard (at this point), whereas Clique Cover is not yet known.

2. Clique Cover is and Chromatic Number is (i.e., reduces to )

3. Chromatic Number is the parent

4. Clique Cover is the child

5. The root of tree is SAT

6. Clique Cover solves Chromatic Number

7. Chromatic Number reduces TO Clique Cover

8. Clique Cover reduces FROM Chromatic Number

9. Conclusion: Clique Cover is as hard as Chromatic Number (see Note at end of point (9) above)

KARP-21 (21 NP-Complete problems; historically Cook-1; Karp-20)

NP-Complete vs. NP-Hard

A crucial distinction: NP-Complete problems must be verifiable in polynomial time (given a proposed solution, we can check it quickly). However, NP-Hard optimization problems cannot easily be verified—how do you confirm that a proposed schedule is optimal without checking all alternatives? You would need exponential time.

Most of Karp’s problems were originally optimization problems (which are NP-Hard), but NP-Completeness requires a decision problem with polynomial verification. This is why Karp needed a transformation strategy.

Optimization vs. Decision: The Threshold Parameter Strategy

Consider an optimization problem: “Find a sequence that minimizes total cost.” The issue: given a proposed sequence, how do you verify it’s optimal? You’d have to try all possible sequences—exponential time!

Karp’s brilliant solution: Add a threshold parameter to convert the optimization problem into a decision problem:

• Original (Optimization): “What is the minimum cost sequence?”
• Modified (Decision): “Does there exist a sequence with cost ?” (or )

Now verification is easy: compute the cost of the proposed sequence and compare it to . This transforms the problem from NP-Hard to NP-Complete.

Example: Job Scheduling (KARP #19)

Imagine you’re a contractor with many tasks (install windows, plumbing, electrical, etc.). Each task has:

• A known duration
• An internal deadline (must finish by a certain date)
• A penalty if the deadline is missed

The optimization question: “What sequence of tasks minimizes total penalty?” (Hard to verify—you’d need to try all permutations.)

Karp’s decision version: “Does there exist a permutation of tasks where total penalties are ?” (Easy to verify—just compute the actual penalties for the proposed sequence.)

By adding the parameter , Karp transforms an intractable optimization problem into a verifiable decision problem, making it NP-Complete.

General Strategy:

In order to define each of the problems presented as a NP-Complete problem, even if the problem inherently is an optimization problem, Karp adds an extra parameter in order to augment the underlying problem:

Considering the underlying NP-Hard optimization problem, the transformed decision problem asks: “Can a solution be found that is <= or >= some supplied threshold parameter ?”

This transformation yields an NP-Complete problem.

Job Sequencing exemplifies this strategy. The optimization version asks “Which permutation of tasks minimizes total penalty?” The decision version asks “Is there a permutation with total penalties ?” where is the user-supplied lateness cost tolerance. Adding this single parameter transforms an optimization problem into a decision problem that can be proven NP-Complete.

Why was chosen as the notation for “reduction” and why do we sometimes find a small “p” after the ?

Reduction involves two problems, one of which is known to be (complexity class) hard and the other problem is not yet known as to its complexity class. The following scenarios will elucidate why was chosen as the symbol to represent reduction.

Alice is Chemistry Professor.

Bob is a Physics Professor.

(Each is an expert in their own field and also knowledgeable about the other field.)

CASE #1: Alice (hard/complex) Bob (?/unsure)

Alice realizes that solving her problem yields a solution to Bob’s problem. What can we assume about the relative complexity of Bob’s problem?

The fact that Alice’s problem solves Bob’s problem does not indicate that Bob’s problem is at least as hard (or harder than) Alice’s problem since Alice’s approach is only one such approach. Maybe there will be an easier approach to solving Bob’s problem. (Analogy: One can always use an exhaustive search (brute-force) to solve a problem, but clearly that does not mean that it is the only way to solve that problem.)

CASE #2: Alice (?/unsure) versus Bob (complex/hard)

Alice realizes that solving her problem yields a solution to Bob’s problem. What can we assume about the relative complexity of Alice’s problem?

If it turns out that there exists an easy solution to Alice’s problem, then in what manner can Bob’s problem be considered hard? Alice’s problem yielded an “easy” solution to Bob’s problem. Since Alice’s problem cannot be Bob’s problem, it must be .

1. In both scenarios, Alice’s problem yields a solution to Bob’s problem. (cf. lines 81 and 90 starting from column G)

2. In both scenarios, Alice’s problem is shown to be Bob’s problem in terms of the complexity costs.

This latter conclusion led to the iconic notation for “reduction” in the literature, but mathematicians rather write than , so we have the following:

(keep in mind who is reducing to whom: )

This notation is read as: reduces to , from to .

On lines #92-93 above, the argument presented to CASE #2’s complexity relationship between Alice’s Problem (unknown at the time) and Bob’s Problem (known to be hard) was based on the following: If Alice’s Problem has an “easy” (in terms of complexity costs) solution to Bob’s Problem (again, hard), in what manner can Bob’s Problem be considered “hard” if an “easy” solution is provided by Alice’s Problem to solve Bob’s hard problem.

We left this argument with an asterisk ( line 93 above) because, in light of Levin’s perspective, we can provide an (albeit rare) situation of exactly that: Alice’s Problem is easy. It solves Bob’s hard problem, and yet no contradiction occurs.

What is this special situation?

As mentioned above Levin was concerned with the intermediary information necessary to solve the other problem (what colloquially I call “the cost of doing business”). Here, the cost of doing business can technically be very great (“hard”) because Alice’s Problem is a Chemistry Problem and Bob’s Problem is a Physics Problem and there is no guarantee that the (chemistry) information Alice’s solution provides can “easily” be used by Bob to solve his hard (physics) problem. In such a case, the “cost of doing business” can be rather complex (“hard”). Mathematically then:

It is precisely because of this that the literature subsequently added the following “footnote” to the symbol for “reduction”:

: This stands for Polynomial, which of course is the basis for “easy” complexities (according to Edmonds). This guarantees us that the “cost of doing business” is “easy” and therefore the argument made on line #93 above holds true.

Under this assumption, then Alice’s Problem must be “hard” as well.

Karp’s Pedagogical Strategy: “Tweaked” Problems and Cousin Pairs (Pages 89–90)

On pages 89–90 of Karp’s 1972 paper, he strategically lists well-known polynomial-time algorithms (problems in class P). Then, as he introduces the KARP-21 NP-Complete problems, he makes a subtle but profound point: Many of the NP-Complete problems are nearly identical to—but slightly different from—the P problems on pages 89–90.

Cousin Pairs: P vs. NP Variants

Karp’s brilliant pedagogical move demonstrates that:

• Cousin in P: A polynomial-time solvable problem (e.g., minimum spanning tree, matching in bipartite graphs)
• Tweaked variant in NP: A seemingly minor modification that makes it NP-Complete (e.g., Steiner tree—requiring specific mandatory vertices; weighted matching in general graphs)

The Thin Boundary Between P and NP

This strategic choice reveals a profound insight: The boundary between tractable (P) and intractable (NP-Complete) problems is surprisingly fragile. A small change in problem specification can move it from polynomial-time solvable to NP-Complete. For example:

• Small modifications to problem constraints (e.g., adding required vertices)
• Subtle changes to optimization objectives (e.g., from unweighted to weighted matching)
• Additional requirements (e.g., from any spanning tree to one passing through specific points)

By intentionally choosing NP-Complete problems that closely resemble solvable P problems, Karp emphasizes how delicate the tractability boundary is—and why the P vs. NP question is so fundamentally important.