NP-Complete and NP-Hard

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.

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.

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.

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.