Lecture 10 - KARP 21 Problems and NP-Hardness Reductions - March 2, 2026

Administrative Updates

Comprehensive notes have been sent covering approximately the next two weeks of lecture material covering various NP-hard problems from the KARP 21 problem set.
Coverage notification: The instructor will email which specific problem the lecture reached (currently through Click Cover). This will help determine which material is relevant for MCQs and exam keywords.
Attendance check: If you did not have a chance to indicate attendance, please text the word “present” and you will be contacted with updates.
Next lecture (Wednesday): Will continue with Problem 19: Job Sequencing. The instructor plans to cover this problem thoroughly and carefully rather than rushing through it.
Job Sequencing preview: This is a scheduling and deadline-based optimization problem requiring organized sequencing of tasks with internal deadlines and associated penalties.

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.

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. 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 paradox is readily solved when you realize that COOK already SHOWED the other direction so Karp only needed to show the second direction, but in terms of definitions, KARP held that two problems must reduce to each other in other to prove that they both have similar hardness in complexity.

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.

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 that “reduces to” but the actual meaning (in Karp’s paper) is the following:

is known to be hard and is unknown
- cf. last lecture’s notes, line 91
solves ‘s problem (that is consistent with the both cases above)
is the parent considered in the reduction tree
- cf. Karp, p. 96, Reduction Tree Summary
is the child (of ) considered in the reduction tree
the root of the entire tree is SATisfiability
- Karp#1
in this context, it is the CHILD () that solves the PARENT’s () problem.
- cf. last lecture’s notes, line 110
reduces TO
- cf. last lecture’s notes, line 106
reduces FROM
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 letters oc with no space between them. 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 ""

Let us take a pair of problems from Karp’s Reduction Tree Summary (Karp, p. 96) and derive these eight pieces of information as they apply to these 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,

Chromatic Number is known to be hard (at this point), whereas Clique Cover is not yet known.
Clique Cover is and Chromatic Number is . (ie reduces to )
Chromatic Number is the parent
Clique Cover is the Child
The root of tree is SAT
Clique Cover solves Chromatic Number
Chromatic Number reduces TO Clique Cover
Clique Cover reduces FROM Chromatic Number
Conclusion. Clique Cover is as hard as Chromatic Number. (See Note at end of #9 above)

Reduction Tree

alt text

KARP-21

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

In order to define each of the problems presented as a NP-Complete problem, even if the problem inherently is an optimization problem and more easily would be classified as a NP-Hard problem (at the very beginning we mentioned that optimization problems generally do not have an easy verification process short of an exhaustive search and therefore typically can only be shown to be Hard and not complete), Karp adds an extra parameter in order to augment the underlying problem:

Considering the underlying NP-Hard optimization problem, Can a solution be found for a related decision problem transformed into this problem by adding an extra threshold parameter and asking if the solution can be found or than supplied parameter.

This then is NP-Complete.

An example of this is in Job Sequencing (Scheduling) KARP#19, which asks for a permutation of a list of tasks such that they (preferably) all make internal deadlines. There exists a penalty parameter (other definitions of this problem discuss in terms of profit) for each task not completed by the internal deadline. Instead of optimization: Which permutation minimizes the tardiness over all (and has least total penalty); instead Karp asks can a permutation of the tasks exist such that the total penalties due to missing deadlines is , where is a user-supplied parameter for lateness cost tolerance. So, by adding this extra parameter , an optimization problem is transformed into a related decision problem and thus can be proven to be NP-Complete in addition to being NP-Hard.

Problem Definitions

KARP#1 - Satisfiability (SAT)

Definition: Given a Boolean predicate , find an assignment of Boolean values (true/false or 1/0) to the variables through such that the predicate evaluates to true.

Key Constraints:

All variables must be Boolean (inputs are 0 or 1)
The output must be Boolean (0 or 1)
No restrictions on how the Boolean operations (AND, OR, NOT) appear in the predicate

Why This Matters: Cook proved that ALL NP problems must reduce to Satisfiability, making it the foundational NP-Complete problem.

Solution Format: A solution can be stored as a bit string of length , where each bit represents the Boolean value assigned to one variable.

KARP#2 - 0/1 Integer Programming

Definition: Given integer constraints and a linear objective function over binary variables (variables that take values 0 or 1), determine if there exists an assignment of 0/1 values to the variables that satisfies all constraints.

Relationship to KARP#1: Like Satisfiability, the solution space consists of bit strings of length . This is why both problems fall into the first grouping—they both use bit strings as their underlying data structure for exhaustive search.

Note: Solutions in 0/1 Integer Programming are similarly stored and generated as bit strings, making the brute-force approach exponential in nature.

KARP#11 - 3-SAT (Satisfiability with Three Literals per Clause)

Definition: A restricted version of Satisfiability where the Boolean predicate must be in Conjunctive Normal Form (CNF):

The predicate is a conjunction (AND) of clauses
Each clause (enclosed in parentheses) is a disjunction (OR) of at most 3 variables
Variables may be negated, but clauses cannot be negated

Formal Structure:

where each clause has at most 3 variables.

Why Clauses Cannot Be Negated: By De Morgan’s Laws, negating a clause would transform the OR operations within that clause into AND operations, violating the CNF structure.

Important Result: Karp proved that any arbitrary Boolean predicate can be written in 3-CNF form without changing the problem’s computational difficulty. This standardized format is called a normal form.

Related Concept - SAT-2: If you restrict to at most 2 variables per clause (instead of 3), the problem becomes solvable in polynomial time and falls into class P. This illustrates how even small changes to problem definitions can dramatically affect computational complexity.

Solution Format: Like Satisfiability, solutions are stored as bit strings of length .

KARP#12 - Chromatic Number

Definition: Given a graph, what is the minimum number of colors needed to color the vertices such that no two adjacent vertices have the same color?

NP-Complete Version: Can a graph be colored with at most colors (where is a user-supplied parameter)?

Reduction Related To: KARP#13 (Clique Cover)

Note: Chromatic Number is the parent problem in this reduction pair and is known to be hard. It reduces to Clique Cover.

KARP#13 - Clique Cover

Definition: Given a graph, find a minimum set of cliques that cover all vertices (a clique is a subset of vertices where every two vertices are adjacent).

NP-Complete Version: Can the vertices of a graph be covered by at most cliques (where is a user-supplied parameter)?

Reduction Related To: KARP#12 (Chromatic Number)

Note: Clique Cover is the child problem in the reduction pair with Chromatic Number. Clique Cover solves the Chromatic Number problem. Through this reduction, we can establish that Clique Cover is as hard as Chromatic Number.

KARP#19 - Job Sequencing (Scheduling)

Definition: Given a set of jobs, each with an associated deadline and a penalty for missing that deadline, find a permutation (sequence) of the jobs.

Optimization Version: Which permutation minimizes the total tardiness over all jobs (and has the least total penalty)?

NP-Complete Version: Can a permutation of the tasks be found such that the total penalties due to missing deadlines is , where is a user-supplied parameter for lateness cost tolerance?

Key Insight: By adding the extra parameter as a threshold, the optimization problem is transformed into a related decision problem, and thus can be proven to be NP-Complete in addition to being NP-Hard.

KARP#21 - The 21 NP-Complete Problems

Summary: Karp’s paper proved that 21 different NP problems are all NP-Complete (historically: Cook proved 1 problem to be NP-Complete; Karp added 20 more, for a total of 21).

General Strategy: For many problems that are inherently optimization problems (and thus difficult to classify as NP-Complete because optimization problems lack easy verification), Karp adds an extra threshold parameter to transform them into decision problems.

Core Principle:

Original optimization problem: “Find a solution that minimizes/maximizes ”
Karp’s decision problem: “Does there exist a solution where is or than the supplied parameter threshold?”

Significance: This transformation technique demonstrates that virtually all of these classic computational problems are equivalent in computational difficulty—they all reduce to one another and form the core set of known NP-Complete problems.