--- title: 'The P vs NP Question' source: 'https://academia.sh/en/courses/theory-of-computation/p-vs-np-question' course: 'Theory of Computation' language: en updated: '2026-08-17T18:08:30+00:00' license: 'CC BY-SA 4.0' --- # The P vs NP Question Stating the open question and laying out the only thing that can be measured: the known lower bound spends 240 steps, meet-in-the-middle 1357, exhaustive search 4321, and the two methods agree on 20 of 20 examples. At input size 24, the lower bound is 24, meet-in-the-middle 8192, exhaustive search 16,777,216; the gap's ratio runs from 341.3 to 699,050.7. At a budget of one million steps, exhaustive search reaches 19 numbers, meet-in-the-middle 37. The question is open, and no direction is claimed in this lesson. 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. ```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 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. ```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 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. ```python 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.