--- title: 'NP-Complete and NP-Hard' source: 'https://academia.sh/en/courses/theory-of-computation/np-complete-and-np-hard' course: 'Theory of Computation' language: en updated: '2026-08-17T18:08:30+00:00' license: 'CC BY-SA 4.0' --- # NP-Complete and NP-Hard Measuring the transfer of difficulty through reduction, in step counts: the transformation that converts a subset sum example into a partition example takes 15 steps, 0.2632 of solving the source. On twenty examples, the reduction takes 300 steps, solving the source 4321, solving the target 19,847, and the two answers agree on 20 of 20 examples. At input size 24, the reduction stays at 27 steps while solving climbs to 16,777,216. What the direction of translation does and does not prove is stated separately. The previous lesson measured a single problem. But most sentences said about difficulty are not about a single problem: they take the form "this problem is at least as hard as that one," comparing two problems. How is such a sentence built, and what does it cost. The tool is **reduction**, introduced in the Advanced Algorithms course: a transformation that converts an example of one problem into an example of another. In that course, reduction was a solving technique — translate into a familiar pattern and use the pattern's method. Here the same transformation is used for a different job: **transferring one problem's difficulty to another.** The method is not retold; it is turned into a number. - **CC20.** The **source problem** is subset sum: does some subset's sum equal the target. The **target problem** is **partition**: can the numbers be split into two halves with equal sums. - **CC21.** A **reduction** is a method that converts an example of the source into an example of the target, and it must **preserve the answer**: if the source is "yes," the target must be "yes"; if the source is "no," the target must be "no." - **CC22.** In the reduction, a step is **copying one element**; three more steps are counted for computing the total and the added element. - **CC23.** The reduction's correctness is **not assumed, it is tested**: on each of the 20 examples the two answers are compared, and the count that agrees is written down. - **CC24.** Three step counts are kept separate: **reduction**, **solving the source**, **solving the target**. Conflating the second and third makes it impossible to see what the reduction is doing. - **CC25.** The reduction's **direction** is stated. A reduction from source to target says the target is **at least as hard** as the source; it says nothing about the reverse direction. - **CC26.** The budget sweep is done at four values: 15, 100, 1000, 10,000 steps. - **CC27.** Examples come from the shared definition's generator: seed **20260218**, 20 examples, 12 numbers per example. There is no second seed. - **CC28.** No problem's NP-completeness is shown by a run. A run measures only **one** reduction's steps and correctness. ## What It Means to Transfer Difficulty How a reduction should be read runs counter to intuition, and misreading it is common. If an example of the source problem is converted into an example of the target problem, then **any method that can solve the target can also solve the source**: translate first, then solve the target, and take the answer as-is. The consequence is this — if a cheap method is found for the target problem, a cheap method would exist for the source problem too. The sentence that follows is about the **target**: the target **cannot be easier** than the source. Translation does not make the source cheaper; it ties the target's chance of being cheap to the source. If the direction is confused, the sentence flips and stops saying anything. Two class names are built on this reading. A problem is **NP-hard** if every problem in class NP can be reduced to it. A problem is **NP-complete** if it is both NP-hard **and** in class NP — that is, if its own "yes" answer has a short certificate. The difference is a single condition: an NP-hard problem does not have to be in class NP, and does not even have to be a decision problem. ## Measuring a Reduction The transformation below does the following: let the sum of the numbers be $T$ and the target be $h$; a single new element is added to the list. This element is chosen so that the sum can be split into two equal halves **only if** a subset summing to $h$ exists in the source. Whether the transformation preserves the answer is not assumed; it is tested on every example. ```python SEED = 20260218 def examples(seed=SEED, n=12, count=20): d = seed result = [] for _ in range(count): numbers = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 numbers.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 result.append({"numbers": numbers, "target": sum(numbers) // 3 + d % 7}) return result def subset_sum_verifier(numbers, target): """Source problem: does some subset sum to the target.""" steps, n = 0, len(numbers) for mask in range(1 << n): steps += 1 if sum(numbers[i] for i in range(n) if mask >> i & 1) == target: return True, steps return False, steps def reduce_(numbers, target): """Converts a subset sum example into a partition example. One step = one element copy; three more steps for the total and the added element.""" total = sum(numbers) new = list(numbers) + [2 * target - total] if 2 * target >= total else \ list(numbers) + [total - 2 * target] return new, len(numbers) + 3 def partition_verifier(numbers): """Target problem: can the numbers be split into two equal-sum halves.""" total = sum(numbers) if total % 2: return False, 1 exists, steps = subset_sum_verifier(numbers, total // 2) return exists, steps + 1 EX = examples() agree, rs, ss, ts = 0, 0, 0, 0 for o in EX: exists1, a1 = subset_sum_verifier(o["numbers"], o["target"]) new, ad = reduce_(o["numbers"], o["target"]) exists2, a2 = partition_verifier(new) agree += exists1 == exists2 rs, ss, ts = rs + ad, ss + a1, ts + a2 print("20 examples, n=12 | answers agree:", agree, "/ 20") print(" reduction:", rs, "steps | solve source:", ss, "steps | solve target:", ts, "steps") print(" reduction to solve-source ratio:", round(rs / ss, 4)) print() o = EX[0] new, ad = reduce_(o["numbers"], o["target"]) exists1, a1 = subset_sum_verifier(o["numbers"], o["target"]) exists2, a2 = partition_verifier(new) print("first example | reduction", ad, "steps | source answer", exists1, f"({a1} steps)", "| target answer", exists2, f"({a2} steps)") print(" ratio:", round(ad / a1, 4)) print() print("budget reduced source solved target solved") for b in (15, 100, 1000, 10000): i1 = sum(1 for x in EX if reduce_(x["numbers"], x["target"])[1] <= b) k1 = sum(1 for x in EX if subset_sum_verifier(x["numbers"], x["target"])[1] <= b) h1 = sum(1 for x in EX if partition_verifier(reduce_(x["numbers"], x["target"])[0])[1] <= b) print(f"{b:5d} {i1:7d} {k1:13d} {h1:13d}") ``` ``` 20 examples, n=12 | answers agree: 20 / 20 reduction: 300 steps | solve source: 4321 steps | solve target: 19847 steps reduction to solve-source ratio: 0.0694 first example | reduction 15 steps | source answer True (57 steps) | target answer True (288 steps) ratio: 0.2632 budget reduced source solved target solved 15 20 0 0 100 20 7 0 1000 20 19 12 10000 20 20 20 ``` ## The Reduction Is Cheap, Solving Is Not The first example places three numbers side by side: **reduction 15 steps**, **solving the source 57 steps**, **solving the target 288 steps**. The reduction is **0.2632** of solving the source. Over the total of twenty examples the ratio falls further: 300 against 4321, that is, **0.0694**. The second pair of numbers is more instructive. Solving the target takes **19,847 steps**, nearly five times solving the source. The translation made **nothing** cheaper; on the contrary, because it added one element to the list, the target example became **more expensive** than the source. Reduction's job is not to make things cheaper. Its job is to build a **bond** between two problems' difficulty, and building that bond comes cheap. The correctness column is the precondition for this bond: the two answers agree on **20 of 20** examples. Had they not agreed, the reduction would be invalid, and its step count would mean nothing. Agreeing on twenty examples does not **prove** the transformation is correct on every input; the transformation's correctness is a justification that comes from how the added element is chosen, and measurement only **tests** that justification. The budget sweep shows three separate behaviors in three columns. The **reduction column is full at budget 15** and still 20 at 10,000; raising the budget adds nothing. Solving the source rises from 0 to 7, to 19, to 20. Solving the target opens later: only **12** at 1000, 20 at 10,000. The same budget stretches less far for the translated example. ## What Remains as Input Size Grows The 0.2632 ratio taken at a single input size does not fully describe the reduction's cheapness. The real question is what the two sides do **relative to each other** as input size grows. ```python print(" n reduction solve source solve target reduction/solve") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {n + 3:9d} {1 << n:12d} {1 << (n + 1):12d}" f" {(n + 3) / (1 << n):15.6f}") ``` ``` n reduction solve source solve target reduction/solve 8 11 256 512 0.042969 12 15 4096 8192 0.003662 16 19 65536 131072 0.000290 20 23 1048576 2097152 0.000022 24 27 16777216 33554432 0.000002 ``` The reduction column is 11, 15, 19, 23, 27: **linear**, one-to-one with input size. The solving columns double at every row. The ratio drops from 0.042969 to **0.000002**. As input size triples, the reduction's share shrinks twenty-thousandfold. The conclusion this table carries is this: the reduction's cost becomes **negligible** next to the difficulty it transfers. If a problem is known to be hard, and it can be converted into another problem by a cheap transformation, whatever can be said about the second problem comes from the first. Difficulty is a **transportable** thing, and the cost of transport is low. ## What a Wrong Translation Looks Like A reduction's cheapness is not, by itself, a virtue. A cheaper transformation that does **not** preserve the answer can always be built, and it cannot be told apart by its cheapness alone. The block below places, next to the correct translation, a translation that outright **discards** the target. The third measurement runs in reverse: a partition example is converted into a subset sum example. ```python SEED = 20260218 def examples(seed=SEED, n=12, count=20): d = seed result = [] for _ in range(count): numbers = [] for _ in range(n): d = (d * 1103515245 + 12345) % 2147483648 numbers.append(d % 97 + 3) d = (d * 1103515245 + 12345) % 2147483648 result.append({"numbers": numbers, "target": sum(numbers) // 3 + d % 7}) return result def subset_sum_verifier(numbers, target): steps, n = 0, len(numbers) for mask in range(1 << n): steps += 1 if sum(numbers[i] for i in range(n) if mask >> i & 1) == target: return True, steps return False, steps def partition_verifier(numbers): total = sum(numbers) if total % 2: return False, 1 exists, steps = subset_sum_verifier(numbers, total // 2) return exists, steps + 1 def correct_reduce(numbers, target): """Answer-preserving transformation: a single equalizing element is added.""" total = sum(numbers) add = 2 * target - total if 2 * target >= total else total - 2 * target return list(numbers) + [add], len(numbers) + 3 def naive_reduce(numbers, target): """Transformation that drops the target: the list is handed to partition as-is.""" return list(numbers), len(numbers) def reverse_reduce(numbers): """Converts a partition example into a subset sum example.""" total = sum(numbers) return list(numbers), total // 2, len(numbers) + 1 print("transformation agree diverge transform steps") for name, f in (("correct", correct_reduce), ("naive ", naive_reduce)): agree = diverge = ca = 0 for o in examples(): k, _ = subset_sum_verifier(o["numbers"], o["target"]) new, steps = f(o["numbers"], o["target"]) h, _ = partition_verifier(new) ca += steps if k == h: agree += 1 else: diverge += 1 print(f"{name:13s} {agree:6d} {diverge:7d} {ca:13d}") print() agree, ta, ha = 0, 0, 0 for o in examples(): new, _ = correct_reduce(o["numbers"], o["target"]) h, a1 = partition_verifier(new) s, target2, steps = reverse_reduce(new) k, a2 = subset_sum_verifier(s, target2) agree += h == k ta, ha = ta + steps, ha + a2 print("reverse direction (partition -> subset sum)") print(" agree:", agree, "/ 20 | transform steps:", ta, "| solve target steps:", ha) ``` ``` transformation agree diverge transform steps correct 20 0 300 naive 8 12 240 reverse direction (partition -> subset sum) agree: 20 / 20 | transform steps: 280 | solve target steps: 19827 ``` The naive translation spends **240 steps**, 60 steps cheaper than the correct one. But it gives the **wrong** answer on 12 of 20 examples. Since it does not preserve the answer, it is not a reduction, and it transfers no difficulty at all. Giving the correct answer on eight examples is no defense either: a transformation either preserves the answer on **every** example or it is invalid. **In a reduction, the work is in the correctness argument, not the step count.** Where the naive translation breaks can also be read off. The partition question always asks about **half** the total; the target in these examples is roughly **a third** of the total. Discarding the target means changing the question, and a changed question gives a different answer. The correct translation's one added element exists precisely to close this gap: the added value moves the half to where the target sits. The reverse direction is shorter: a partition example is converted into a subset sum example, with the target set to half the total, in **280 steps**, and the answer is preserved on **20 of 20** examples. Read together, the two directions give this result: these two problems reduce to each other **mutually**, meaning a cheap method for one makes the other cheap too. In terms of difficulty, these two problems cannot be separated. ## What the Run Does Not Say No number measured in this lesson shows that the partition problem is NP-complete. All that is shown is that **one** problem reduces to it. The definition of NP-hardness requires **every** problem in class NP to be reducible to it; this is a quantifier no finite run can cover. That these two problems are NP-complete is a result of the theory, and it enters here **as a result of the theory**; none of the tables above prove it. What measurement actually proves is smaller and more concrete: this transformation preserved the answer on 20 of 20 examples, took 15 steps, and its share fell as input size grew. This is the sentence that can be written in a report. The sentence "partition is NP-complete" rests not on measurement but on a **source**, and it is not written without citing that source. The reverse direction must also be stated plainly. A reduction built from source to target supports that the target is **at least as** hard as the source. It says nothing about **how much** harder the target could be at most, and it never says the source is easy. Reading a bond built in one direction as if it held in both is the most common mistake on this topic. ## Summary - A reduction is an answer-preserving transformation that converts an example of one problem into an example of another; its direction says the target cannot be easier than the source. - In the first example, reduction takes 15 steps, solving the source 57, solving the target 288; the ratio is 0.2632. Over twenty examples, 300 against 4321 and 19,847. - The translation makes nothing cheaper: because the target example carries one more element, it is five times more expensive to solve than the source. - The two answers agree on 20 of 20 examples; this is a test, not proof that the transformation is correct on every input. - As input size rises from 8 to 24, the reduction goes from 11 to 27 steps, solving from 256 to 16,777,216, and the ratio falls to 0.000002. - NP-hard is a problem every NP problem can be reduced to; NP-complete adds to that being in class NP itself. Neither can be shown by a finite run. ## Next Step Everything measured up to this point pointed in the **yes** direction: a certificate verified a "yes"; a reduction carried a "yes." The next lesson measures the missing direction. When an answer is "no," what can be shown, and is what can be shown the same length. It will count how many steps a "no" proof needs while a "yes" certificate closes in 13 steps on twenty examples, and why some "no" answers close cheaply.