The P vs NP Question

Four class names and the known relationships between them have been established. What remains is the most talked-about, least answered question: is everything verifiable also solvable. This lesson states that question and does not try to measure what it cannot measure.

Why the question cannot be measured stays visible throughout the lesson. Measurement is a finite run, and a finite run can only say “this method spent this many steps.” The question, though, carries a quantifier over all methods: “does no method exist.” The distance between these two sentences is this lesson’s subject. The only thing that can be measured is the gap between the best known method and the known lower bound.

• CC38. The question is this containment relationship: is class P equal to the whole of class NP. That P sits inside NP was established in 02; what is asked is the reverse direction.
• CC39. The question is open. No direction is claimed in this lesson, considered likely, or called “expected.”
• CC40. A known lower bound is a shown step count that no method can go below. The lower bound used here is the weakest one: since a decision cannot be made without reading the input, at least n steps.
• CC41. The best known method is whichever of the methods built in this lesson spends the fewest steps. The word “known” is read relative to this course’s scope; whether a better one exists outside the course is not measured here.
• CC42. The second method is meet-in-the-middle: the input is split in two, all of the first half’s subset sums are written into a table, and the second half is queried against that table.
• CC43. The correctness of meet-in-the-middle is not assumed; it is compared against exhaustive search’s answer on every example.
• CC44. A step is one subset for exhaustive search, one subset or one query for meet-in-the-middle, and one number read for the lower bound.
• CC45. The budget sweep is done at four values: 13, 100, 1000, 10,000 steps. The second sweep is over input size.
• CC46. Examples come from the shared definition’s generator, seed 20260218. There is no second seed.
• CC47. A gap narrowing does not count as a sign of direction. The narrowing is measured, not interpreted.

The Question Itself

The statement is short and unambiguous. P is the class of decision problems solved in a number of steps bounded by a polynomial in input size. NP is the class of problems whose “yes” answer is verified within the same bound. Since every solved problem is verifiable, P sits inside NP. What is asked is: is there a problem inside NP that is not in P.

One direction of the question has been established, and it is easy to show. The other direction could close in two ways: either a polynomial-step method is found for an NP-complete problem and the two classes coincide, or it is proven that polynomial steps are insufficient for such a problem and they separate. Neither has been done, and this lesson says nothing about which will happen.

Why a run cannot close this question is equally clear. A method spending 4096 steps does not show that 4096 steps are required for that problem; it only shows that that method spent that many. A lower-bound proof, by contrast, speaks about every method, and no run can exhaust every method. This course’s ban on overclaiming exists exactly to guard this gap.

The Only Thing That Can Be Measured

The block below places three numbers side by side: the known lower bound, the steps of the best method built in this course, and exhaustive search’s steps. Meet-in-the-middle’s answer is compared against exhaustive search 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 brute_force(numbers, target):
    """One step = one subset."""
    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 meet_in_middle(numbers, target):
    """Input is split in two; every half's subset sums are worked out
    and the second half is queried against them. One step = one subset or one query."""
    n = len(numbers)
    left, right = numbers[: n // 2], numbers[n // 2:]
    steps, table = 0, set()
    for mask in range(1 << len(left)):
        steps += 1
        table.add(sum(left[i] for i in range(len(left)) if mask >> i & 1))
    for mask in range(1 << len(right)):
        steps += 1
        t = sum(right[i] for i in range(len(right)) if mask >> i & 1)
        if target - t in table:
            return True, steps
    return False, steps


EX = examples()
agree, bfs, mms, lbs = 0, 0, 0, 0
for o in EX:
    y1, a1 = brute_force(o["numbers"], o["target"])
    y2, a2 = meet_in_middle(o["numbers"], o["target"])
    agree += y1 == y2
    bfs, mms, lbs = bfs + a1, mms + a2, lbs + len(o["numbers"])
print("20 examples, n=12 | two methods agree:", agree, "/ 20")
print("  known lower bound:", lbs, "steps | meet-in-the-middle:", mms,
      "steps | exhaustive search:", bfs, "steps")
print()
print("budget  exhaustive search  meet-in-the-middle")
for b in (13, 100, 1000, 10000):
    c1 = sum(1 for o in EX if brute_force(o["numbers"], o["target"])[1] <= b)
    c2 = sum(1 for o in EX if meet_in_middle(o["numbers"], o["target"])[1] <= b)
    print(f"{b:5d}  {c1:10d}  {c2:15d}")
print()
print(" n  lower bound  meet-in-middle  exhaustive search  meet/lower bound  search/lower bound")
for n in (8, 12, 16, 20, 24):
    mim = (1 << (n - n // 2)) + (1 << (n // 2))
    print(f"{n:2d}  {n:9d}  {mim:7d}  {1 << n:10d}  {mim / n:17.1f}"
          f"  {(1 << n) / n:16.1f}")

20 examples, n=12 | two methods agree: 20 / 20
  known lower bound: 240 steps | meet-in-the-middle: 1357 steps | exhaustive search: 4321 steps

budget  exhaustive search  meet-in-the-middle
   13           0                0
  100           7               20
 1000          19               20
10000          20               20

 n  lower bound  meet-in-middle  exhaustive search  meet/lower bound  search/lower bound
 8          8       32         256                4.0              32.0
12         12      128        4096               10.7             341.3
16         16      512       65536               32.0            4096.0
20         20     2048     1048576              102.4           52428.8
24         24     8192    16777216              341.3          699050.7

Reading the Gap

Three numbers side by side: lower bound 240, meet-in-the-middle 1357, exhaustive search 4321. The second method spends less than a third of the first and gives the same answer on 20 of 20 examples. This is an improvement, it was measured, and it is real.

The budget sweep shows where the improvement pays off. At budget 100, exhaustive search stays at 7 examples while meet-in-the-middle gives 20 of 20. At budget 1000, exhaustive search rises to 19; at 10,000 both are full. So there is a budget range where the improvement is visible, and outside that range the two methods cannot be told apart.

The input-size table answers the real question: does the gap close. The meet-in-the-middle column is 32, 128, 512, 2048, 8192 — quadrupling at every row. The exhaustive search column goes from 256 to 16,777,216, multiplying by sixteen at every row. The ratios to the lower bound climb from 4.0 to 341.3, and from 32.0 to 699,050.7.

What must be read is that both columns grow. The improvement did not reduce the ratio; it reduced the rate of growth. At twenty-four numbers, meet-in-the-middle is 2048 times cheaper than exhaustive search, but still 341 times more expensive than the lower bound. The gap narrowed, it did not close, and this table carries no sign that it will close — nor any sign that it will not.

Does the Improvement Hold in Both Directions

The 3.18-fold gain on the yes set could partly come from stopping early: exhaustive search stops once it finds a matching subset, and this gives it a real discount, not an unfair advantage. Whether the gain comes from structure or from stopping early is measured on a set where stopping early never happens. Lesson 04’s unstructured no examples are exactly that.

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 brute_force(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 meet_in_middle(numbers, target):
    n = len(numbers)
    left, right = numbers[: n // 2], numbers[n // 2:]
    steps, table = 0, set()
    for mask in range(1 << len(left)):
        steps += 1
        table.add(sum(left[i] for i in range(len(left)) if mask >> i & 1))
    for mask in range(1 << len(right)):
        steps += 1
        t = sum(right[i] for i in range(len(right)) if mask >> i & 1)
        if target - t in table:
            return True, steps
    return False, steps


def unreachable(numbers):
    """Setup step: an unreachable target is chosen; the answer is definitely 'no'."""
    reached = {0}
    for x in numbers:
        reached |= {u + x for u in reached}
    return min((t for t in range(1, sum(numbers)) if t not in reached),
               key=lambda t: abs(t - sum(numbers) // 3))


EX = examples()
YES = [(o["numbers"], o["target"]) for o in EX]
NO = [(o["numbers"], unreachable(o["numbers"])) for o in EX]
print("set    agree  exhaustive search  meet-in-middle  ratio")
for name, batch in (("yes  ", YES), ("no   ", NO)):
    agree = bfs = mms = 0
    for s, h in batch:
        y1, a1 = brute_force(s, h)
        y2, a2 = meet_in_middle(s, h)
        agree += y1 == y2
        bfs, mms = bfs + a1, mms + a2
    print(f"{name}  {agree:6d}  {bfs:10d}  {mms:7d}  {round(bfs / mms, 2):5}")

set    agree  exhaustive search  meet-in-middle  ratio
yes        20        4321     1357   3.18
no         20       81920     2560   32.0

On the no set, neither method can stop early, so both do the whole of their work. Exhaustive search spends 81,920, meet-in-the-middle 2560 steps, a ratio of 32.0. This is ten times the 3.18 on the yes set. The conclusion is: the source of the gain is not stopping early, it is the method’s structure; the ratio looking low on the yes set is because exhaustive search gets a discount there.

This distinction bears on the open question. Whether an improvement is genuinely structural can only be seen by measuring it on a discount-free set. Even so, the 32.0 ratio, too, points to no direction: an exponential divided by a constant factor is still an exponential, and the table already showed this with a 341-fold distance at twenty-four numbers.

How Far You Get with a Fixed Budget

The engineering counterpart of the improvement is not the ratio but the input size reached. A step budget can be fixed, and the largest input size each method can handle within that budget computed. The table below carries a third column, and that column is hypothetical: what would happen if a quadratic-step method were found. No claim is made that such a method exists; the column only shows what the question would change.

def largest_n(budget, cost, upper=200000):
    """The largest input size that stays within budget."""
    best = 0
    for n in range(1, upper + 1):
        if cost(n) <= budget:
            best = n
    return best


def scan(n):
    return 1 << n


def meet(n):
    return (1 << (n - n // 2)) + (1 << (n // 2))


def quadratic(n):
    return n * n


print("step budget      exhaustive search  meet-in-middle  hypothetical n^2")
for b in (10 ** 4, 10 ** 6, 10 ** 8, 10 ** 10):
    print(f"{b:14d}  {largest_n(b, scan):10d}  {largest_n(b, meet):7d}"
          f"  {largest_n(b, quadratic):15d}")

step budget      exhaustive search  meet-in-middle  hypothetical n^2
         10000          13       24              100
       1000000          19       37             1000
     100000000          26       50            10000
   10000000000          33       64           100000

As the budget rises ten-thousandfold, exhaustive search’s reach goes from 13 to 33: the budget grows tens of thousands of times, input size gains twenty numbers. Meet-in-the-middle, over the same budgets, goes from 24 to 64, meaning at every budget it stretches to roughly twice the input size of exhaustive search. This is a real, measured gain.

The third column shows the nature of the difference. The hypothetical quadratic method, over the same budgets, goes from 100 to 100,000. The first two columns gain a handful of numbers by growing the budget; the third gains orders of magnitude. The engineering counterpart of the P vs NP question is the gap between these two behaviors: the first and second columns belong to the same family, the third belongs to a different one, and which family the subset sum problem belongs to is not known.

What This Lesson Does Not Say

None of the numbers above points in a direction, and none should be read as if it did. Meet-in-the-middle beating exhaustive search 2048-fold does not suggest something better will be found; meet-in-the-middle staying 341 times away from the lower bound does not suggest it will not. Measurement is not the kind of thing that could support either sentence.

What can be said is exactly this. The best method built in this lesson spent 1357 steps at 12 numbers; the known lower bound was 240 steps; the ratio between them rose to 341.3 at input size 24. This sentence is measured and written with its budget attached. The sentence “subset sum cannot be solved in polynomial time” is not measured, has not been proven in this course, and has not been proven by anyone; writing it would violate the rule.

The same strictness applies to the reverse direction. The sentence “one day a polynomial method will be found” is not measured either. The only honest sentence that can be written about an open question is the sentence stating that the question is open.

The Engineering Counterpart

The question staying open does not leave an engineer without work; on the contrary, it makes clear what to do. If a problem is known to reduce to an NP-complete problem, searching for a general, cheap solution to it is the same thing as trying to solve an unsolved question in the theory. This does not mean it cannot be done; it means correctly naming what is being attempted.

In practice three paths remain, and all three have been or will be measured in this course. The first is keeping the input small: the budget table showed which method suffices at 12 numbers. The second is improving the method: meet-in-the-middle doubled the input size reached. The third is giving up on an exact solution, and this is the subject of the next lesson.

Summary

• The P vs NP question asks whether a problem exists inside NP that is not in P, and it is open; this lesson claims no direction.
• A finite run cannot close the question, because it measures one method’s steps and cannot speak about every method.
• On twenty examples the known lower bound is 240, meet-in-the-middle 1357, exhaustive search 4321 steps; the two methods agree on 20 of 20 examples.
• As input size rises from 8 to 24, meet-in-the-middle goes from 32 to 8192, exhaustive search from 256 to 16,777,216; the ratio to the lower bound climbs from 4.0 to 341.3 and from 32.0 to 699,050.7. The gap narrowed, it did not close.
• At a budget of one million steps, exhaustive search reaches 19 numbers, meet-in-the-middle 37; a hypothetical quadratic method would have reached 1000.
• The only honest sentence that can be written about an open question is one that states the measured gap with its budget and says the question is open.

Next Step

This lesson left the third path open: giving up on an exact solution. The next lesson counts its cost. On how many examples does an approximate solution find the exact result, how far off does it fall when it doesn’t, and when the budget given to the approximate method is grown, does the loss really close. The course’s and the Computer Science curriculum’s final lesson ends with this question.