--- title: 'Theory of Computation' source: 'https://academia.sh/en/courses/theory-of-computation' language: en updated: '2026-08-17T04:39:45+00:00' license: 'CC BY-SA 4.0' lessons: 10 outcomes: - 'Separates finite automata, production rules and the universal model by measured examples' - 'Defines the classes P, NP, NP-complete, NP-hard and co-NP through reduction and certificates' - 'Writes a result together with its budget and does not put observation in the place of proof' --- # Theory of Computation Measuring models of computation and complexity classes by what a finite budget can and cannot answer. ## Models of Computation The languages finite automata can recognize, the limit production rules cross, the universal model, and the step budget's inadequacy in the face of undecidability. ### Finite Automata Source: https://academia.sh/en/courses/theory-of-computation/finite-automata Measuring the state budget by exhaustive count: in a universe of 31 strings, 1-state automata recognize 2 distinct languages, 2-state ones 26, 3-state ones 1054; against the 2-to-the-31 languages that could be written over that universe, this is a share of 0.0000004908. The Advanced Algorithms course deliberately left two questions open. In the traveling salesman and Hamiltonian path lessons, the question "why is this problem hard" was referred to this course in a dedicated section each; the course's closing then asked: for some problems, is not knowing anything better than brute force a fact **about our knowledge, or about the problems themselves**. Both debts look at the same place. The first asks about the difficulty of a single problem, the second about where difficulty stands in general. That course's final measurement showed that testing a candidate path costs 11 steps, while showing that no such path exists costs an average of 11,601 steps — and as was stated plainly there, this was an **observation**, not a proof. Naming the observation and saying where it turns into a proof is this course's job. This course is not a speed course. What it asks is not how many steps a procedure spends, but what a **model** can never do at all. But a theory's results cannot be proved by running them. This is why what is measured here is not the theory itself, but **what a finite budget can and cannot say.** In every lesson, three numbers sit side by side: the budget, what the budget answers, and what it fails to answer. The course's rule follows from this: a result's number is written **together with its budget**, and an unsolvability claim whose budget is not written counts as unmeasured. A finite run never says "this language cannot be recognized" anywhere; it can only say **it was not recognized for this k**. #### State Count as Budget The first model is the one that has the least. A **finite automaton** reads its input once, from left to right, keeps nothing it has read, and sits in only one of a finite number of **states** at any time. It has no memory; the state count takes memory's place. The definition of a state machine was established in the State lesson of the Design Patterns course and in the Modeling and Representation course and is not repeated here; the question here is different: **how many languages can be recognized.** - **MC1** — The alphabet has two symbols. The universe is the finite set of all **strings** not exceeding a given length limit, and the empty string is in the universe. The universe of strings not exceeding length 4 contains 31 strings. - **MC2** — A **language** is a subset of the universe. The number of languages that can be written over a 31-string universe is $2^{31}$. - **MC3** — The automaton is built **deterministic**: the start state is 0, the transition table assigns a single state to every state-symbol pair, and the accepting set is a subset of the states. A string is recognized if the state reached after reading it is in the accepting set. - **MC4** — **All** k-state automata can be counted: the combination of $k^{2k}$ transition tables with $2^k$ accepting sets. 2 automata for k=1, 64 for k=2, 5832 for k=3. - **MC5** — The measure is an **exhaustive count**: there is no estimate, no sampling. No measurement in this course uses `random` or `time`; what is measured is steps, not duration. A concrete example settles the definition. A two-state automaton can hold the answer to "is the number of a's read so far even" in its state: every a flips the state, every b leaves it as it is, and the accepting set is the even state. This automaton neither stores the input nor reads it back; yet it correctly classifies every string of every length. This is what it means to **recognize** a language: deciding whether a string is in the language, with finite memory and a single pass. ```python """Finite automaton: ALL k-state automata are counted, the languages they recognize are collected.""" from itertools import product ALPHABET = ("a", "b") def strings(max_length): output = [""] for n in range(1, max_length + 1): output += ["".join(d) for d in product(ALPHABET, repeat=n)] return output def run_automaton(transitions, accepting, string, start=0): state = start for symbol in string: state = transitions[(state, symbol)] return state in accepting def automata(k): """All k-state deterministic automata: transition table x accepting set.""" cells = [(state, symbol) for state in range(k) for symbol in ALPHABET] for targets in product(range(k), repeat=len(cells)): transitions = dict(zip(cells, targets)) for accept_mask in range(1 << k): accepting = {i for i in range(k) if accept_mask >> i & 1} yield transitions, accepting def recognizable_languages(k, universe): """The number of DISTINCT languages recognized by k-state automata over the universe.""" languages = set() for transitions, accepting in automata(k): languages.add(frozenset(s for s in universe if run_automaton(transitions, accepting, s))) return languages U = strings(4) print("universe: number of strings not exceeding length 4 =", len(U)) print("states automata distinct languages share of universe's writable languages") for k in (1, 2, 3): languages = recognizable_languages(k, U) print(f" {k:3d} {sum(1 for _ in automata(k)):6d} {len(languages):16d}" f" {len(languages) / 2 ** len(U):.10f}") print("total number of languages writable over the universe: 2^31 =", 2 ** 31) ``` ``` universe: number of strings not exceeding length 4 = 31 states automata distinct languages share of universe's writable languages 1 2 2 0.0000000009 2 64 26 0.0000000121 3 5832 1054 0.0000004908 total number of languages writable over the universe: 2^31 = 2147483648 ``` Three numbers side by side. **Budget:** state count 1, 2, 3 — 2, 64, and 5832 automata respectively. **What the budget answers:** these automata settle **2**, **26**, and **1054** distinct languages over the 31-string universe. **What the budget fails to answer:** $2^{31} - 1054$ languages remain; the three-state budget's share is **0.0000004908**. As the budget rises to 5832 automata, the recognized-language count rises from 2 to 1054, a 527-fold increase. The covered share, by contrast, rises from one in a billion to half in a million. The model class grows, and **the ratio is still close to zero.** The second point worth noting is that 5832 automata produce only 1054 distinct languages: most automata are copies of one another, because unreachable states and equivalent states rewrite the same language. #### What Changes as the Budget Grows The ratio above was measured in a single universe, and a ratio measured in a single universe is not a result. A budget sweep is mandatory in this course: every measurement is repeated at **at least three budget values**, and whether the result changes with the budget is recorded. The second axis swept here is the universe's length limit. - **MC6** — The budget sweep is done along two axes: **state count** and **the universe's length limit**. A budget's adequacy can only be read once both are written together. ```python """Budget sweep: as the universe grows, how much does the same state budget cover.""" from itertools import product ALPHABET = ("a", "b") def strings(max_length): output = [""] for n in range(1, max_length + 1): output += ["".join(d) for d in product(ALPHABET, repeat=n)] return output def run_automaton(transitions, accepting, string): state = 0 for symbol in string: state = transitions[(state, symbol)] return state in accepting def automata(k): cells = [(state, symbol) for state in range(k) for symbol in ALPHABET] for targets in product(range(k), repeat=len(cells)): transitions = dict(zip(cells, targets)) for accept_mask in range(1 << k): yield transitions, {i for i in range(k) if accept_mask >> i & 1} def recognizable_languages(k, universe): return {frozenset(s for s in universe if run_automaton(transitions, accepting, s)) for transitions, accepting in automata(k)} print("length strings k=1 k=2 k=3 languages in universe share k=3 covers") for length in (1, 2, 3, 4): U = strings(length) counts = [len(recognizable_languages(k, U)) for k in (1, 2, 3)] print(f"{length:6d} {len(U):7d} {counts[0]:3d} {counts[1]:3d} {counts[2]:4d}" f" {2 ** len(U):20d} {counts[2] / 2 ** len(U):.10f}") ``` ``` length strings k=1 k=2 k=3 languages in universe share k=3 covers 1 3 2 8 8 8 1.0000000000 2 7 2 26 116 128 0.9062500000 3 15 2 26 690 32768 0.0210571289 4 31 2 26 1054 2147483648 0.0000004908 ``` This table is a lesson's result on its own. In the three-string universe with length limit 1, three-state automata recognize **every language**: the covered share is **1.0000000000**. At length 2 the share is 0.9062500000, at length 3 it is 0.0210571289, at length 4 it is 0.0000004908. Same budget, same model, four measurements — and the whole path between "sufficient" and "nothing." **A budget's adequacy is not a property of the budget; it is a relationship between the budget and the universe.** The second column is even more instructive. Two-state automata recognize 26 languages at length 2, and **still 26** at lengths 3 and 4. As the universe rises from 7 strings to 31, the recognized-language count does not move at all. This saturation is not a measurement flaw: because the number of distinguishable states with two states is exhausted, every new string added to the universe falls into one of the 26 languages that already exist. Growing the budget sometimes changes everything, sometimes nothing; and which one it is can only be seen by measuring. #### How Many States Are Needed to Recognize a Language Until now the question was "how many languages does k states recognize." The reverse is more useful: **how many states, at minimum, does a given language require.** The tool for this is the **residual language**: which suffixes, after a given prefix, put the string into the language. If two prefixes carry the same residual language, no automaton is required to separate them; if they carry different residual languages, an automaton is required to put them in different states. The count of distinct residual languages is called a **distinguishability class**. - **MC7** — A prefix's residual language is the set of suffixes in the universe that, when appended after that prefix, put the string into the language. - **MC8** — Only a suffix whose **both extensions stay in the universe** can separate two prefixes. A suffix that goes past the length limit does not force the automaton into anything. - **MC9** — The exhaustive count is made cheaper here: accepting sets are not scanned separately; once a transition table is given, the accepting decision each string requires is collected, and if no conflict arises, that table suffices. The result is the same as trying accepting sets one by one. ```python """Residual language, distinguishability class, and exhaustive count side by side.""" from itertools import product ALPHABET = ("a", "b") def strings(max_length): output = [""] for n in range(1, max_length + 1): output += ["".join(d) for d in product(ALPHABET, repeat=n)] return output def residual_language(prefix, target, universe): """Which suffixes, after the prefix, put the string into the language.""" return frozenset(s for s in universe if prefix + s in target) def distinguishability_classes(target, universe): """Shared definition's tool: the number of distinguishability classes.""" prefixes = {s[:i] for s in universe for i in range(len(s) + 1)} return len({residual_language(p, target, universe) for p in prefixes}) def separated_prefixes(target, universe): """Only a suffix whose BOTH extensions stay in the universe can separate two prefixes.""" universe_set = set(universe) prefixes = sorted({s[:i] for s in universe for i in range(len(s) + 1)}, key=lambda p: (len(p), p)) signature = {p: tuple((1 if p + s in target else 0) if p + s in universe_set else -1 for s in universe) for p in prefixes} selected = [] for p in prefixes: if all(any(x >= 0 and y >= 0 and x != y for x, y in zip(signature[p], signature[q])) for q in selected): selected.append(p) return len(selected) def recognizer_exists(k, target, universe): """All k-state transition tables are scanned; the accepting set is chosen for consistency.""" cells = [(state, symbol) for state in range(k) for symbol in ALPHABET] for targets in product(range(k), repeat=len(cells)): transitions = dict(zip(cells, targets)) required, consistent = {}, True for s in universe: state = 0 for symbol in s: state = transitions[(state, symbol)] wanted = s in target if required.setdefault(state, wanted) != wanted: consistent = False break if consistent: return True return False def smallest_k(target, universe, upper=5): for k in range(1, upper + 1): if recognizer_exists(k, target, universe): return k return None def even_a(s): return s.count("a") % 2 == 0 def ends_with_ab(s): return s.endswith("ab") print("language length strings class separated prefix exhaustive") for name, predicate in (("even a's ", even_a), ("ends with ab ", ends_with_ab)): for length in (2, 3, 4): U = strings(length) target = frozenset(s for s in U if predicate(s)) print(f"{name} {length:7d} {len(U):4d} {distinguishability_classes(target, U):4d}" f" {separated_prefixes(target, U):12d} {smallest_k(target, U):9d}") ``` ``` language length strings class separated prefix exhaustive even a's 2 7 5 2 2 even a's 3 15 7 2 2 even a's 4 31 9 2 2 ends with ab 2 7 4 3 3 ends with ab 3 15 6 3 3 ends with ab 4 31 9 3 3 ``` Three columns say three separate things, and two of them correct each other. The class count grows as 5, 7, 9 for the "even a's" language; yet the exhaustive count shows that an automaton exists that recognizes the same language with **two states**. The difference comes from the universe's cutoff: prefixes close to the length limit get artificially separated because their suffixes run past the edge of the universe. **The class count is an over-count** and cannot be read as the state count on its own. The separated-prefix count accounts for this cutoff and matches the exhaustive count exactly in all six measurements — this is an agreement, not a proof, and the budget it was tested at goes up to length limit 4. This correction is the course's own rule applied to itself. Class counting is a cheap calculation and the exhaustive count is expensive; whether the cheap calculation stands in for the expensive one is not assumed, it is **tested**. The same path is followed in the next three lessons: the cheap measure is written first, then compared against the exhaustive count within a budget, and where it diverges is not hidden. The concept of a regular language is established here not by definition but by measurement. A language is regular if the required state count **does not grow as the universe grows**: "even a's" stays at 2 across all three universes, "ends with ab" stays at 3. For these two languages a fixed budget can be chosen, and the chosen budget suffices at every length. The next lesson applies the same three measures to a language that does not carry this property. #### Summary - A finite automaton's budget is its state count; all k-state deterministic automata can be counted, and there are 2, 64, and 5832 of them for k=1, 2, 3 respectively. - Over the 31-string universe of length at most 4, these automata recognize 2, 26, and 1054 distinct languages; the number of languages writable over the universe is 2 to the 31, and three states cover a share of 0.0000004908. - The budget sweep shows that a budget's adequacy depends on the universe: three states cover the whole universe at length limit 1, and half in a million at length limit 4. - The number of languages two-state automata recognize freezes at 26 past length 2; growing the universe changes nothing for this budget. - The count of residual-language classes is an over-count: for "even a's" the class count comes out to 9, while the exhaustive count shows two states suffice; both extensions of a distinguishing suffix must stay in the universe. - A language is regular if the required state count does not grow with the universe; it stays constant across all three universes for these two languages. #### Next Step The next lesson applies the same three measures to a language that requires counting: strings with an equal number of a's followed by an equal number of b's. What will be asked is this: if the required state count grows with the universe, is growing the budget a solution, or is it not the budget but the **model class** that needs to change. The answer comes when a three-line production rule does what an entire family of automata cannot. ### Context-Free Languages Source: https://academia.sh/en/courses/theory-of-computation/context-free-languages Measuring languages the state budget cannot cover: the state count required for the equal-a's-and-b's language grows as 3, 5, 7, 9, 11 with the length limit, while a one-line production rule generates the same language exactly, and the rule's description never grows. The previous lesson established the measure that counts a language as regular: if the required state count does not grow as the universe grows, a fixed budget can be chosen for that language. Two examples passed this measure; "even a's" wanted 2 states across all three universes, "ends with ab" wanted 3. Now a language that does not pass the measure is examined. The language in question is: some number of a's, followed by **exactly the same number** of b's. This language demands a counting task; the number of a's read must be held somewhere so the b's can be counted against it. A finite automaton's only memory is its state, and the state count is fixed. The whole weight of the question is here. #### A Language That Requires Counting The previous lesson's three measures are used exactly as they were: the count of residual-language classes, the separated-prefix count, and the exhaustive count. All three run over the same universe, then the universe is swept. A second language is placed alongside: the **balanced string**, that is, a string where, counting a as an open and b as a close, no prefix ever has more closes than opens, and the two are equal at the end. - **MC10** — The target language `equal_count`: a string belongs to the language if its first half is all a's, its second half is all b's, and its length is even. The empty string belongs to the language. - **MC11** — The second target `balanced` is tested with a single counter: a increments it, b decrements it; the counter never drops below zero and is zero at the end. - **MC12** — The exhaustive count in this lesson runs from k=1 to 5. The number of five-state transition tables is $5^{10}$; this is the measure's budget, and k=6 was not tried in this lesson. - **MC13** — The measurement never says "this language cannot be recognized" anywhere. The only thing it can say is what was found within the k values and length limits tried. ```python """a^n b^n and the balanced language: class, separated prefix and exhaustive count side by side.""" from itertools import product ALPHABET = ("a", "b") def strings(max_length): output = [""] for n in range(1, max_length + 1): output += ["".join(d) for d in product(ALPHABET, repeat=n)] return output def equal_count(s): """Is it of the form a^n b^n.""" n = len(s) if n % 2: return False half = n // 2 return s[:half] == "a" * half and s[half:] == "b" * half def balanced(s): """a opens, b closes; no prefix ever has more closes than opens.""" counter = 0 for c in s: counter += 1 if c == "a" else -1 if counter < 0: return False return counter == 0 def distinguishability_classes(target, universe): """Distinguishability classes: the number of residual languages.""" prefixes = {s[:i] for s in universe for i in range(len(s) + 1)} return len({frozenset(t for t in universe if p + t in target) for p in prefixes}) def separated_prefixes(target, universe): """Only a suffix whose BOTH extensions stay in the universe can separate two prefixes.""" universe_set = set(universe) prefixes = sorted({s[:i] for s in universe for i in range(len(s) + 1)}, key=lambda p: (len(p), p)) signature = {p: tuple((1 if p + t in target else 0) if p + t in universe_set else -1 for t in universe) for p in prefixes} selected = [] for p in prefixes: if all(any(x >= 0 and y >= 0 and x != y for x, y in zip(signature[p], signature[q])) for q in selected): selected.append(p) return len(selected) def recognizer_exists(k, target, universe): """All k-state transition tables; the accepting set is chosen for consistency.""" cells = [(state, symbol) for state in range(k) for symbol in ALPHABET] for targets in product(range(k), repeat=len(cells)): transitions = dict(zip(cells, targets)) required, consistent = {}, True for s in universe: state = 0 for symbol in s: state = transitions[(state, symbol)] wanted = s in target if required.setdefault(state, wanted) != wanted: consistent = False break if consistent: return True return False print("length strings a^n b^n: class prefix balanced: class prefix") for length in (2, 4, 6, 8, 10): U = strings(length) h1 = frozenset(s for s in U if equal_count(s)) h2 = frozenset(s for s in U if balanced(s)) print(f"{length:6d} {len(U):6d} {distinguishability_classes(h1, U):15d} {separated_prefixes(h1, U):5d}" f" {distinguishability_classes(h2, U):15d} {separated_prefixes(h2, U):5d}") print() print("exhaustive count: k = 1..5, ALL automata tried") print("length a^n b^n target smallest recognizing k") for length in (2, 3, 4): U = strings(length) h = frozenset(s for s in U if equal_count(s)) k = [i for i in (1, 2, 3, 4, 5) if recognizer_exists(i, h, U)] print(f"{length:6d} {str(sorted(h)):28s} {k[0] if k else 'none'}") ``` ``` length strings a^n b^n: class prefix balanced: class prefix 2 7 4 3 4 3 4 31 6 5 7 4 6 127 8 7 11 5 8 511 10 9 16 6 10 2047 12 11 22 7 exhaustive count: k = 1..5, ALL automata tried length a^n b^n target smallest recognizing k 2 ['', 'ab'] 3 3 ['', 'ab'] 3 4 ['', 'aabb', 'ab'] 5 ``` Three numbers side by side. **Budget:** state count 1 to 5, length limit 2 to 10. **What the budget answers:** the required state count grows as **3, 5, 7, 9, 11** for the a's-then-b's language, as **3, 4, 5, 6, 7** for the balanced language; at length 4 the exhaustive count finds the smallest k to be **5**, matching the separated-prefix count exactly. **What the budget fails to answer:** that no fixed k suffices at **any** length. The measurement cannot say this; what it can say is that within the five lengths and five k values tried, the state count keeps growing without stopping. The cause of the growth is in the language, not in the measurement. Consider first the prefixes made only of a's: the two distinct prefixes `a` and `aa` are separated by the suffix `b`, because `ab` belongs to the language and `aab` does not; and both extensions are inside the universe. The same holds for `aa` and `aaa` with the suffix `bb`, and for `aaa` and `aaaa` with the suffix `bbb`. In a universe with length limit 2m, this chain stretches to m+1 prefixes, and every prefix in the chain demands a separate state. The chain gets longer as the limit grows. The statement here, precisely, is: **for every fixed k, a length was measured at which that k does not suffice**; the statement "it never suffices" is the theory's result and is not established by a run. The first two rows of the exhaustive-count table should also be read. In the length-2 and length-3 universes, the target stays the same, because no odd-length string belongs to the language; the smallest k is 3 in both. At length 4, the moment `aabb` enters the target, the count **jumps to 5**. That is, the required state count rises not with the number of strings added to the universe, but with **a new counting depth** being added to the language. The two-state automaton's memory ran out at one bit; what is required here is a counter that holds how many a's were read, and the number of values the counter can take rises with the length. The one-off difference between the class column and the prefix column shows that the previous lesson's over-count continues: for the a's-then-b's language, the class is 4, 6, 8, 10, 12 while the separated prefix is 3, 5, 7, 9, 11. The two columns have the same **slope**; both grow linearly. For the balanced language, though, the two columns diverge — the class rises to 22 while the prefix stays at 7 — the gap between the cheap measure and the tested measure varies by language, and this is why the cheap measure is never written on its own. #### A Production Rule Does What the Automaton Cannot Growing the budget is one path. The second path is changing the model. A **production rule** is a rule that permits replacing a symbol with a string; applying rules one after another is called **derivation**. A language whose every string can be derived from a finite set of rules is called a **context-free language**. Grammar and parsing were established in the Compilation Stages lesson of the How Computers Work course; tokens, the abstract syntax tree, and the embedding of operator precedence into the tree were explained there and are not repeated here. The only thing this lesson adds is the measure: whether the set a rule generates is **exactly identical** to the target language. - **MC14** — The rule `S -> a S b | empty` carries two options and is a single line. Derivation depth is how many times the rule is applied. - **MC15** — The second rule `S -> a S b S | empty` generates balanced strings. The measurement is whether the generated set equals the set of balanced strings in the universe; a subset is not enough. - **MC16** — The rule's **description** and **run** are measured separately: the description is the line count, the run is the derivation depth. ```python """Production rule: the description stays constant, the derivation depth grows with the input.""" from itertools import product ALPHABET = ("a", "b") RULE = {"S": [("a", "S", "b"), ()]} # S -> a S b | empty def strings(max_length): output = [""] for n in range(1, max_length + 1): output += ["".join(d) for d in product(ALPHABET, repeat=n)] return output def equal_count(s): n = len(s) if n % 2: return False half = n // 2 return s[:half] == "a" * half and s[half:] == "b" * half def balanced(s): counter = 0 for c in s: counter += 1 if c == "a" else -1 if counter < 0: return False return counter == 0 def derive(max_depth): """Strings generated by the rule in at most `max_depth` steps.""" generated = {""} previous = {""} for _ in range(max_depth): new_set = {"a" + s + "b" for s in previous} generated |= new_set previous = new_set return generated def derive_balanced(max_length): """S -> a S b S | empty; all derivations not exceeding max_length.""" set_, changed = {""}, True while changed: changed = False for x in list(set_): for y in list(set_): new_string = "a" + x + "b" + y if len(new_string) <= max_length and new_string not in set_: set_.add(new_string) changed = True return set_ print("S -> a S b | empty") print("depth generated longest covers same-length target") for d in (1, 2, 3, 4, 5): U = derive(d) target = {s for s in strings(2 * d) if equal_count(s)} print(f"{d:5d} {len(U):9d} {max(len(s) for s in U):7d} {target <= U}") print(" generated at depth 3:", sorted(derive(3))) print() print("S -> a S b S | empty") print("length generated balanced strings same set") for length in (2, 4, 6, 8): T = derive_balanced(length) D = {s for s in strings(length) if balanced(s)} print(f"{length:6d} {len(T):9d} {len(D):16d} {T == D}") ``` ``` S -> a S b | empty depth generated longest covers same-length target 1 2 2 True 2 3 4 True 3 4 6 True 4 5 8 True 5 6 10 True generated at depth 3: ['', 'aaabbb', 'aabb', 'ab'] S -> a S b S | empty length generated balanced strings same set 2 2 2 True 4 4 4 True 6 9 9 True 8 23 23 True ``` The one-line rule generates `""`, `ab`, `aabb`, `aaabbb` in three derivation steps; this is **the entirety** of the a's-then-b's strings in the universe of length at most 6. The same result continues up to length 10 at five levels of depth: the coverage column reads `True` in all five rows. For the second rule the measure is stricter, because what is tested is not a subset but **equality**: the 23 strings generated up to length 8 are exactly the 23 balanced strings in the universe. This is the opposite of what the previous section measured. For the same language, while the automaton's required state count rose from 3 to 11, the rule's line count **stayed at 1**. Changing the model class is **a different thing entirely** from growing the budget: the former keeps the description's size fixed, the latter grows the description. #### Where the Budget Goes The cost the two models pay does not sit in the same place. The table below places the two sections' numbers side by side; the state column comes from the separated-prefix count, the depth column from the derivation measurement. | Length limit | Automaton: states required | Rule: lines | Rule: derivation depth | |---|---|---|---| | 2 | 3 | 1 | 1 | | 4 | 5 | 1 | 2 | | 6 | 7 | 1 | 3 | | 8 | 9 | 1 | 4 | | 10 | 11 | 1 | 5 | What grows in the automaton is the **description**: a bigger machine has to be written for longer strings, and the machine itself grows along with the input. What grows in the rule is the **run**: the rule stays the same, it is only applied more times. When measuring a model's power, the question to ask should not be "how many steps does it spend," but **"what grows along with the input."** This distinction has a cost too, and it is not hidden. A rule does not decide whether a string belongs to the language with a finite automaton's single pass; it has to search for the derivation, and searching is more expensive than a single pass. The measurement shows this too: generating the 23 strings for the balanced language up to length 8 required continuing the iteration until the set settled at a fixed point. Power does not come for free; what is paid, in place of description size, is search. #### Summary - For the language requiring an equal count of a's and b's, the required state count grows with the length limit as 3, 5, 7, 9, 11; for the balanced language, as 3, 4, 5, 6, 7. - In the length-4 universe, all automata from k=1 to 5 were tried, and the smallest k came out to **5**; this number is exactly the same as the separated-prefix measure. - That no fixed k suffices at any length was not measured and cannot be measured; what is measured is that, for every k tried, a length was found at which that k does not suffice. - The one-line rule `S -> a S b | empty` generates every target string of length at most 6 in three derivation steps; `S -> a S b S | empty` generates all 23 balanced strings up to length 8, and nothing extra. - What grows with the input is the description in an automaton, the run in a production rule; changing the model class is a different thing from growing the budget. - The cost of the power was measured too: the rule does not decide in a single pass, it searches for the derivation; description size is gained, search is paid. #### Next Step Both models were defined with a limit: one by state count, the other by rule form. The next lesson loosens the limit as much as possible and builds a model with a tape that can **overwrite** the symbol it reads and move back and forth. The question to be asked is: can we count all the members of this model one by one, and once counted, can we learn how many of them halt with a step budget. The first half of the answer is easier than expected, the second half is harder than expected. ### Turing Machine Source: https://academia.sh/en/courses/theory-of-computation/turing-machine Measuring the tape model by exhaustive count: 9784 of 20,736 2-state, 2-symbol machines halt, the longest halting run takes 6 steps and the count does not change at all when the budget is raised from 6 to 200; of the 10,952 machines that do not halt, 5040 are settled by a loop certificate. The previous two lessons drew a limit with two models. A finite automaton reads its input in a single pass, and its memory is as large as its state count; a production rule generates more without growing its description, but requires a search to decide. Both share the same gap: **they cannot change what they read.** This lesson loosens the limit as much as possible. The model has a **tape** that extends without bound in both directions; a symbol sits in every cell of the tape, and the machine reads the cell it is on, writes over it, moves one step right or left, and changes its state. This model's name is the **Turing machine**, and the theory uses this name. Per the course's rule, only the name is mentioned here: the person is not described, and the name appears in no code identifier. The only information the name carries is which concept in the theory the definition below corresponds to. #### Tape and Machine The tape by itself is not a new power, but a new form of **memory**. In a finite automaton, memory was bounded by the state count and could not grow with the input; on a tape, memory grows over the course of the run. The machine's **description**, by contrast, is still finite: once the state count and symbol count are given, the transition table's row count is fixed. This means a budget, and a budget means an exhaustive count. - **MC17** — The tape is empty in both directions; an empty cell carries the symbol 0, and a cell with 0 written on it is indistinguishable from a cell never written to. The alphabet has two symbols. - **MC18** — A cell's content is a triple: the symbol to write, the direction to move, the new state. If the new state is k, the machine **halts**; the start state is 0, and the machine starts on a blank tape. - **MC19** — **All** k-state, two-symbol machines can be counted. The transition table has 2k cells, and each cell takes one of $2 \cdot 2 \cdot (k+1)$ options. 64 machines for k=1, 20,736 for k=2. - **MC20** — The budget is **steps**. One step consists of reading one cell, writing, and moving. Duration is not measured. - **MC21** — The "known to halt" count is **cumulative**: a machine seen to halt at a small budget is not counted again at a larger budget. ```python """Machine family running on a tape: ALL k-state, 2-symbol machines.""" from itertools import product WRITE = (0, 1) MOVE = (-1, 1) def machines(k): """Cell: (symbol to write, move, new state). New state k means HALT.""" cell = [(w, m, s) for w in WRITE for m in MOVE for s in range(k + 1)] positions = [(state, symbol) for state in range(k) for symbol in (0, 1)] for choice in product(cell, repeat=len(positions)): yield dict(zip(positions, choice)) def run(machine, k, budget): """Blank tape. Returns: (halted, steps, number of 1s written to the tape).""" tape = {} position, state, step = 0, 0, 0 while step < budget: symbol = tape.get(position, 0) write, move, next_state = machine[(state, symbol)] tape[position] = write position += move step += 1 if next_state == k: return True, step, sum(tape.values()) state = next_state return False, step, sum(tape.values()) def budget_sweep(k, budgets): all_machines = list(machines(k)) known = set() print(f"k = {k} states, machine count {len(all_machines)}") for b in budgets: for i, m in enumerate(all_machines): if i not in known and run(m, k, b)[0]: known.add(i) print(f" budget {b:4d} known to halt {len(known):6d}" f" unknown {len(all_machines) - len(known):6d}") return all_machines BUDGETS = (1, 3, 6, 7, 10, 50, 200) budget_sweep(1, BUDGETS) all_machines = budget_sweep(2, BUDGETS) print() distribution = {} best = None for m in all_machines: halted, step, ones = run(m, 2, 200) if halted: distribution[step] = distribution.get(step, 0) + 1 if best is None or (step, ones) > (best[1], best[2]): best = (m, step, ones) print("step distribution of halting machines:", dict(sorted(distribution.items()))) print("longest halting run:", best[1], "steps ,", best[2], "ones") print("transition table:", {f"s{s}y{y}": v for (s, y), v in best[0].items()}) print() print("step state next position tape") tape, position, state, step = {}, 0, 0, 0 while step < 200: symbol = tape.get(position, 0) write, move, next_state = best[0][(state, symbol)] tape[position] = write position += move step += 1 display = "".join(str(tape.get(p, 0)) for p in range(min(tape), max(tape) + 1)) print(f"{step:4d} {state:5d} {next_state:4d} {position:5d} {display}") if next_state == 2: break state = next_state ``` ``` k = 1 states, machine count 64 budget 1 known to halt 32 unknown 32 budget 3 known to halt 32 unknown 32 budget 6 known to halt 32 unknown 32 budget 7 known to halt 32 unknown 32 budget 10 known to halt 32 unknown 32 budget 50 known to halt 32 unknown 32 budget 200 known to halt 32 unknown 32 k = 2 states, machine count 20736 budget 1 known to halt 6912 unknown 13824 budget 3 known to halt 9600 unknown 11136 budget 6 known to halt 9784 unknown 10952 budget 7 known to halt 9784 unknown 10952 budget 10 known to halt 9784 unknown 10952 budget 50 known to halt 9784 unknown 10952 budget 200 known to halt 9784 unknown 10952 step distribution of halting machines: {1: 6912, 2: 2304, 3: 384, 4: 128, 5: 16, 6: 40} longest halting run: 6 steps , 4 ones transition table: {'s0y0': (1, -1, 1), 's0y1': (1, 1, 1), 's1y0': (1, 1, 0), 's1y1': (1, -1, 2)} step state next position tape 1 0 1 -1 1 2 1 0 0 11 3 0 1 1 11 4 1 0 2 111 5 0 1 1 1111 6 1 2 0 1111 ``` Three numbers side by side. **Budget:** step budget 1 to 200, family size 64 and 20,736. **What the budget answers:** in the two-state family, **9784** machines were seen to halt; in the one-state family, **32**. **What the budget fails to answer:** in the two-state family, **10,952** machines did not halt at this budget, and this number **did not change at all** when the budget was raised from 6 to 200. The real information the budget sweep gives is the saturation point. The count is 6912 at step 1, 9600 at step 3, 9784 at step 6, and **constant from there on**. The step distribution shows this in a single line: 6912 machines halt in one step, 2304 in two, and only 40 machines halt in six steps. That every halting run in this family takes at most 6 steps is a known result of the theory; the measurement **agrees** with this result, it does not establish it. The 6912 in the first row can also be calculated, and calculating it tests the measurement's correctness. Because the machine starts on a blank tape, the first cell read is always the intersection of state 0 and symbol 0. That cell has 12 options, and in 4 of them the new state is the halting state; that is, exactly one third of all machines halt on the very first step. One third of 20,736 is 6912, and the table gives exactly this. The measurement hitting an expected number does not verify it, but missing it would have shown a flaw; this kind of check is sought for every number in this course. The final table is one machine's trace, and it shows what the tape is for. The machine starts on a blank tape, writes to the left on the first step, then turns right, and halts on the sixth step after writing 1 to four cells. Steps three and five, where it visits the same cell twice, deserve attention: the machine reads what it wrote earlier and makes its decision based on that. A finite automaton has no counterpart to this. #### A Single Procedure Runs Every Machine There is a single procedure that does every run above: `run`. The machine is not embedded inside this procedure; it is supplied **as an argument**. Each of the 20,736 machines is a transition table, that is, data, and a single procedure executes the whole of this data. This is the model's defining property: one machine's description can be another machine's input. This is why this model is counted as **universal** — because it can carry a program as data. From here follows the theory's most frequently cited claim. The **Church–Turing thesis** states that everything intuitively called "computable by a procedure" is computable with this model. The word "thesis" in the name is not an accident: this is **not a proven proposition**; it is a correspondence established between a formal model and the informal notion of "procedure." It cannot be proved, because one of its two sides is undefined; it can be tested, because every newly proposed model has so far computed the same set as this model. Universality also has a measurable side. The previous lesson established a distinction: what grows with the input was the description in the automaton, the run in the production rule. In the tape model, the description **never grows**: a two-state machine's transition table is four lines, and it stays four lines no matter how many cells are written on the tape. The only thing that grows is the run — the step count and the number of cells used. This shows plainly where the power comes from: a finite description, an unbounded working area. The practical consequence the thesis brings to this lesson is this: if **this model** cannot decide a question, then searching for a procedure that can decide it is also pointless. What the next section measures sits exactly at the edge of this limit. #### Can a Proof Say What the Budget Cannot "Did not halt at this budget" and "never halts" are not the same statement, and the second is never written from a single run in this course. But sometimes a **proof** can be extracted from within a run. Because the tape is blank in both directions, the machine's configuration depends only on the state and the position of the 1's on the tape, **relative to the head**. If the same configuration occurs a second time, the machine repeats the movement in between forever; if it did not halt in the first cycle, it will not halt in any cycle. This is not an observation, it is an inference. - **MC22** — A configuration is the pair `(state, set of cells carrying a 1, relative to the head)`. A cell written with 0 is indistinguishable from a blank cell. - **MC23** — A repeated configuration is a **loop certificate**; the machine never halts on that run. - **MC24** — Failing to find a certificate says nothing. The result splits into three sets: `halted`, `loop`, and `unknown`. - **MC25** — The loop scan is swept too: it is repeated at budgets 10, 50, and 200. - **MC26** — Cycle detection in a graph was established in the Data Structures course and is not explained again here; the only difference here is that the nodes are not given in advance and are generated during the run. ```python """How many of the machines the budget cannot answer are settled by a CERTIFICATE.""" from itertools import product WRITE = (0, 1) MOVE = (-1, 1) def machines(k): cell = [(w, m, s) for w in WRITE for m in MOVE for s in range(k + 1)] positions = [(state, symbol) for state in range(k) for symbol in (0, 1)] for choice in product(cell, repeat=len(positions)): yield dict(zip(positions, choice)) def resolve(machine, k, budget): """Returns: ('halted' | 'loop' | 'unknown', steps). The tape is blank in both directions; so if the same configuration, shifted relative to position, occurs a second time, the machine repeats the same movement forever. """ tape = {} position, state, step = 0, 0, 0 seen = {(0, frozenset())} while step < budget: symbol = tape.get(position, 0) write, move, next_state = machine[(state, symbol)] tape[position] = write position += move step += 1 if next_state == k: return "halted", step state = next_state signature = (state, frozenset(p - position for p, v in tape.items() if v)) if signature in seen: return "loop", step seen.add(signature) return "unknown", step for k in (1, 2): all_machines = list(machines(k)) print(f"k = {k} states, machine count {len(all_machines)}") latest = 0 for budget in (10, 50, 200): tally = {"halted": 0, "loop": 0, "unknown": 0} for m in all_machines: result, step = resolve(m, k, budget) tally[result] += 1 if result == "loop": latest = max(latest, step) print(f" budget {budget:4d} halted {tally['halted']:6d}" f" loop certified {tally['loop']:6d}" f" unknown {tally['unknown']:6d}") print(f" latest step a loop was caught at: {latest}") ``` ``` k = 1 states, machine count 64 budget 10 halted 32 loop certified 16 unknown 16 budget 50 halted 32 loop certified 16 unknown 16 budget 200 halted 32 loop certified 16 unknown 16 latest step a loop was caught at: 1 k = 2 states, machine count 20736 budget 10 halted 9784 loop certified 5040 unknown 5912 budget 50 halted 9784 loop certified 5040 unknown 5912 budget 200 halted 9784 loop certified 5040 unknown 5912 latest step a loop was caught at: 8 ``` Alongside the 9784 machines the budget settles in the two-state family, **5040** machines settled by the certificate are added. **5912** machines remain, and this lesson says nothing about them. Most of the remainder are machines that drift in one direction on the tape: because they write to a new cell every step, their configuration never repeats, even though a human eye looking at them can see that they do not halt. The proof tool's scope is exactly as large as the pattern it looks for. Splitting into three sets is itself this course's method. A two-set report — only "halted" and "did not halt" — would turn the measurement into a verdict; the third set keeps a written record of where the verdict stops. The same structure shows up in the one-state family too: 32 halted, 16 certified, 16 unknown. When the family grew 324-fold, the ratios changed, but the third set **never emptied**. The same numbers come out at all three budgets, and the reason is in the last line: a loop is caught at the latest by **step 8**. That is, there is no difference at all between budget 10 and budget 200 for this measure. In the same lesson, two separate budget sweeps gave two separate results: the halting scan saturated at 6, the loop scan at 8. **The saturation point is a property of the question, not of the budget.** #### Summary - A tape machine can write to the cell it reads and move in both directions; its memory grows over the course of the run, while its description stays finite. - All machines in two-symbol families can be counted: 64 machines in the one-state family, 20,736 in the two-state family. - When the step budget is swept, the halting-machine count progresses as 6912, 9600, 9784 and saturates at step 6; raising the budget to 200 does not change this number at all. - The longest halting run takes 6 steps and writes four 1's to the tape; that the upper bound in this family is 6 is a result of the theory, and the measurement merely agrees with it. - A single run procedure executes all 20,736 machines; a machine's description is data, and this is why the model is counted as universal. - Of the 10,952 machines that do not halt within the budget, 5040 are settled by a loop certificate based on repeated configuration; the measurement says nothing about the remaining 5912. #### Next Step In this lesson, the "halted" count came from a budget, and the "never halts" count came from a certificate, and the sum of the two did not close the family. The next lesson asks whether this gap is a coincidence. On a one-line rule, the budget will be swept from 5 to 200, all one thousand starting points will be seen to halt, and right at that point the lesson's most important sentence will be written: observation is not proof. ### Undecidability Source: https://academia.sh/en/courses/theory-of-computation/undecidability Measuring that observation is not proof: on a one-line counter rule, 7 of 1000 starting points halt at budget 5, 1000 of 1000 at budget 200, but the same budget fails to settle 9 of 5000 starting points, and a starting point that fools every budget can be found. The previous lesson split the two-state machine family into three sets: 9784 machines halted, 5040 machines were certified to never halt, and nothing was said about 5912 machines. The existence of the third set may look like a shortfall; this lesson shows that it is not. To do this, the machine family is set aside and a single rule is examined. The rule is one line and simple enough for a child to understand: if the number is odd, multiply by three and add one; if even, divide by two; stop once the number is 1. The rule has neither branching depth nor a stored state. The gap between the rule's brevity and the unpredictability of its behavior is this lesson's entire subject. #### A One-Line Rule, Unpredictable Behavior The measure is set up the same way as in the previous lessons. The budget is the step count, the universe is the set of starting numbers, and how many starting points halt at each budget value is counted **cumulatively**. - **MC27** — The rule is a single line and carries no option: for a given number, the next number is unique. It is a deterministic rule, containing no randomness. - **MC28** — The universe is the integers from 1 up to an upper limit. In the first measurement, the upper limit is 1000. - **MC29** — The budget is the step count. When the budget runs out, the run is cut off, and the result for that starting point counts as **unknown**; "does not halt" is not written. - **MC30** — Steps spent are also totaled separately, because a budget's cost cannot be read unless it sits alongside the result. - **MC31** — The highest of the intermediate values is recorded. The rule's output is not a straight descent; it grows first. ```python """One-line counter rule: sweeping the step budget.""" def counter_run(n, budget): """3n+1 if n is odd, n/2 if even. Halts once n = 1.""" step, highest = 0, n while n != 1 and step < budget: n = 3 * n + 1 if n % 2 else n // 2 highest = max(highest, n) step += 1 return {"halted": n == 1, "step": step, "highest": highest} def budget_sweep(budgets, upper=1000): known = set() print(f"one-line counter rule, {upper} starting points") print("budget known to halt unknown steps spent") for b in budgets: spent = 0 for n in range(1, upper + 1): r = counter_run(n, b) spent += r["step"] if r["halted"]: known.add(n) print(f"{b:5d} {len(known):15d} {upper - len(known):10d} {spent:13d}") budget_sweep((5, 20, 50, 100, 200)) longest = max(range(1, 1001), key=lambda n: counter_run(n, 1000)["step"]) r = counter_run(longest, 1000) print(f"longest run: n = {longest} -> {r['step']} steps ," f" highest intermediate value {r['highest']}") ``` ``` one-line counter rule, 1000 starting points budget known to halt unknown steps spent 5 7 993 4985 20 155 845 19159 50 569 431 37815 100 756 244 54426 200 1000 0 59542 longest run: n = 871 -> 178 steps , highest intermediate value 190996 ``` Three numbers side by side. **Budget:** 5, 20, 50, 100, 200 steps. **What the budget answers:** the number of settled starting points is **7**, 155, 569, 756, and **1000**. **What the budget fails to answer:** 993, 845, 431, 244, and finally 0 starting points. In the previous lesson's machine family, growing the budget changed nothing past step 6. Here the opposite happens: as the budget rises 40-fold, the number of settled starting points rises from 7 to 1000, a 142-fold increase. **Growing the budget sometimes changes nothing, sometimes everything, and which one it is can only be seen by measuring.** The cost was measured too: from 4985 steps to 59,542, a twelvefold increase. The last line shows why the rule is unpredictable. The longest run, for n=871, takes 178 steps, and the intermediate value in that run climbs to **190,996**. That is, a sequence starting at 871 rises to 219 times its starting value before dropping to 1. The rule itself is one line; its behavior jumps this much depending on the starting point. And right here, the lesson's most important sentence must be written. **All 1000 of 1000 starting points halting is not proof that all of them will halt.** The table says only this: each of the thousand starting points tried dropped to 1 in at most 200 steps. It says nothing about the ones not tried, and the next section shows with a number that this is not an idle worry. #### Same Budget, Different Universe A budget being "sufficient" is not a property of the budget. In the first lesson, this was measured by three-state automata recognizing every language at length limit 1 and half in a million at length limit 4. The same measure is repeated here: the budget is held fixed, the universe is grown. - **MC32** — The universe sweep sets the upper limit to 1000, 2000, and 5000. The budget is fixed at 200. - **MC33** — A **bounded decider** is a procedure that says "does not halt" when the budget runs out. This procedure can be wrong, and the starting point where it is wrong is found by searching. - **MC34** — That a starting point halts can also be shown **by proof**: if the number is a power of two, it is halved on every step and drops to 1 in a number of steps equal to the exponent. This is not a run result but a reading of the rule. ```python """Same budget, different universe: adequacy is not a property of the budget.""" def counter_run(n, budget): step = 0 while n != 1 and step < budget: n = 3 * n + 1 if n % 2 else n // 2 step += 1 return n == 1 print("budget 200, universe sweep") print(" upper known to halt unknown") for upper in (1000, 2000, 5000): b = sum(1 for n in range(1, upper + 1) if counter_run(n, 200)) print(f"{upper:5d} {b:15d} {upper - b:10d}") print() print("smallest starting point that fools each budget") for budget in (5, 20, 50, 100, 200, 300): n = 1 while counter_run(n, budget): n += 1 print(f" budget {budget:4d} -> n = {n}") print() powers = [n for n in range(1, 1001) if n & (n - 1) == 0] print("settled by certificate: powers of two") print(" up to 1000,", len(powers), "starting points ,", "test is a single comparison, longest run", max(len(bin(n)) - 3 for n in powers), "steps") print(" do they all really halt:", all(counter_run(n, 1000) for n in powers)) ``` ``` budget 200, universe sweep upper known to halt unknown 1000 1000 0 2000 2000 0 5000 4991 9 smallest starting point that fools each budget budget 5 -> n = 3 budget 20 -> n = 25 budget 50 -> n = 27 budget 100 -> n = 27 budget 200 -> n = 2463 budget 300 -> n = 26623 settled by certificate: powers of two up to 1000, 10 starting points , test is a single comparison, longest run 9 steps do they all really halt: True ``` The first table breaks the previous section's result. Budget 200 suffices for a thousand out of a thousand starting points, and two thousand out of two thousand; at five thousand starting points, it fails to settle **9 of them**. The sentence "budget 200 suffices" tells nothing without the universe being written. The second table is sharper. For every budget, a starting point was found that fools the decider working with that budget: 3 for budget 5, 25 for budget 20, 27 for budget 100, **2463** for budget 200, **26,623** for budget 300. The fooling starting point moves farther away as the budget grows, but it does not disappear. What the measurement says is exactly this: **for all six of the six budgets tried, a counterexample was found.** That such an example exists for every budget cannot be drawn from this table; that is the theory's job, not the measurement's. The third block shows information coming from an entirely different source. For powers of two, halting is known without running: every step halves the number, and it drops to 1 in a number of steps equal to the exponent. This **proof** is tested with a single comparison and covers **10 starting points** up to 1000. The run, by contrast, covers 1000 starting points by spending 59,542 steps. The proof is cheap and narrow, the run is expensive and wide; the two give different kinds of information, and neither stands in for the other. The cheap test in the Advanced Algorithms course also worked in only one direction; the one here is the same. #### Two Answers and Three Answers A bounded decider has two designs, and the difference between them can be measured. The first says "does not halt" when the budget runs out, and produces an answer for every starting point. The second says "unknown" when the budget runs out, and leaves some starting points without an answer. The two do exactly the same run, spend the same steps; the only place they differ is the sentence at the moment the budget runs out. - **MC35** — The reference answer is taken from a 100,000-step budget. Because every starting point in this universe halts under 300 steps, the reference is certain **for this universe**; the same cannot be said for a larger universe. - **MC36** — The wrong count is the number of starting points where the decider's answer diverges from the reference. "Unknown" does not count as an answer, and is not counted as wrong. ```python """Comparing a two-answer decider with a three-answer one in the same universe.""" def counter_run(n, budget): step = 0 while n != 1 and step < budget: n = 3 * n + 1 if n % 2 else n // 2 step += 1 return n == 1, step def two_answer(n, budget): """Says 'halts' or 'does not halt' when the budget runs out. Can be wrong.""" halted, _ = counter_run(n, budget) return "halts" if halted else "does not halt" def three_answer(n, budget): """Says 'unknown' when the budget runs out. Never wrong, but does not always answer.""" halted, _ = counter_run(n, budget) return "halts" if halted else "unknown" UPPER = 5000 truth = {n: counter_run(n, 100000)[0] for n in range(1, UPPER + 1)} print(f"universe {UPPER} starting points, true answer taken from a 100000-step run") print("budget two-answer: wrong three-answer: wrong unknown steps spent") for budget in (5, 20, 50, 100, 200, 300): wrong2 = wrong3 = unknown = spent = 0 for n in range(1, UPPER + 1): spent += counter_run(n, budget)[1] a2, a3 = two_answer(n, budget), three_answer(n, budget) if (a2 == "halts") != truth[n]: wrong2 += 1 if a3 == "unknown": unknown += 1 elif (a3 == "halts") != truth[n]: wrong3 += 1 print(f"{budget:5d} {wrong2:19d} {wrong3:20d} {unknown:10d} {spent:13d}") ``` ``` universe 5000 starting points, true answer taken from a 100000-step run budget two-answer: wrong three-answer: wrong unknown steps spent 5 4993 0 4993 24985 20 4758 0 4758 98948 50 3110 0 3110 218633 100 1666 0 1666 332345 200 9 0 9 387867 300 0 0 0 387968 ``` Same budget, same run, same steps — two separate outcomes. The two-answer design is wrong on **4993** starting points at budget 5; 9 at budget 200, 0 at budget 300. The three-answer design is never wrong at any budget: the wrong column reads **0** in all six rows. The price it pays is the starting points it leaves unanswered, and this number is exactly the same as the wrong column's. So the third answer is not a loss of information; it is **giving the wrong answer its correct name.** The last column says one more thing. As the budget rises from 200 to 300, steps spent rise from 387,867 to 387,968, an increase of only 101 steps — because only 9 starting points exceed 200 steps. The cost of closing the remaining uncertainty is **three in ten thousand**, next to the whole budget spent up to that point. Not closing uncertainty where it closes cheaply is a design flaw; but that it is cheap in this universe does not mean it will be cheap in every universe. #### Why the Halting Problem Is Undecidable Everything measured so far was for a single rule. The **halting problem** is more general than this: given a program's description and a given input, saying whether that program will halt. That this problem is **undecidable** is a proven result of the theory, and the sketch below is the shape of that proof; no run in this lesson establishes it. Suppose there is a `decide` procedure that gives the correct answer for every program description and every input. Then a second procedure can be written: `opposite`, which takes a description it is given, calls `decide` on that description, giving the description itself as the input; if the answer is "halts," it loops forever, if the answer is "does not halt," it halts immediately. Now let `opposite` be called with its own description. If `decide` says "halts," `opposite` starts looping, meaning it does not halt. If it says "does not halt," `opposite` halts immediately. In both cases, the assumed procedure has given the wrong answer. Since the assumption produces a contradiction, no such procedure exists. The power of this proof is that it appeals to no budget at all. In the previous section, a counterexample was **searched for and found** for every budget; the proof, on the other hand, does not search — it shows that a single procedure cannot exist. The thesis cited in the previous lesson is useful here: the result does not concern a single model, but the concept of "procedure" itself, because the thesis binds every reasonable model to the same set. The engineering counterpart of this result is: for a large portion of questions about a program's behavior, there is no procedure that gives the **correct answer for every program**. Whether two programs give the same output, that a piece of code will never run, that a loop will terminate — all of these contain the halting problem, and all fall under the scope of the same result. This does not mean analysis tools are useless; what it says is that such a tool has to give **three answers, not two**. The previous lesson's three-way split into `halted`, `loop`, and `unknown` was exactly this, and that third set is not an arbitrary shortfall — it is the result itself. One of the two debts left by the Advanced Algorithms course was paid here. For some questions, not knowing the answer can be a fact **about the problems** rather than **about our knowledge**, and the halting problem is the proven example of this. The second debt — why nothing better than brute force is known — is still open: what is asked there is not whether a problem can be solved, but **how fast** it can be solved. #### Summary - On the one-line counter rule, of 1000 starting points, 7 are settled at budget 5, 155 at 20, 569 at 50, 756 at 100, and 1000 at 200; steps spent rise from 4985 to 59,542. - The longest run, for n=871, takes 178 steps and the intermediate value rises to 190,996; the rule is one line, the behavior is unpredictable. - All 1000 of 1000 starting points halting is not proof that all of them will halt. - The same budget of 200 settles all starting points at 1000 and 2000, but fails to settle 9 of them at 5000; for all six of the six budgets tried, a fooling starting point was found. - A proof is cheap and narrow: halting for powers of two is known with a single comparison and covers 10 starting points up to 1000; a run covers 1000 starting points with 59,542 steps. - That the halting problem is undecidable is a result of the theory, not of a run; the result's practical counterpart was measured: a two-answer decider is wrong 4993 times at budget 5 across 5000 starting points, while the three-answer design doing the exact same run has a wrong count of zero at all six budgets. #### Next Step The Models of Computation topic showed one side of the limit: for some questions, the answer cannot be given by **any** procedure at all. The next topic takes up the other side. There, every problem will be decidable, and the only question will be **in how many steps**. Complexity Classes takes on the second debt left by the Advanced Algorithms course, and first builds the easiest class: decision problems solvable in polynomial time. ## Complexity Classes Polynomial time, verifiability and certificates, transferring difficulty through reduction, the asymmetry of complement problems, an open question, and the measured deviation of approximate solutions. ### Class P Source: https://academia.sh/en/courses/theory-of-computation/class-p Measuring decision problems solvable in polynomial time under a finite step budget: on the same 20 examples, the threshold problem is decided in 12 steps, the pair problem in 66, while subset sum requires a budget of 10,000 steps. As input size rises from 8 to 20, the first two methods' worst-case steps go from 8 to 20 and from 28 to 190, while the third rises from 256 to 1,048,576. The difference between the decision problem class and the growth class from the Algorithms course is stated separately. The Models of Computation topic asked whether a question can be answered at all, and measured that a finite budget cannot always close that question. The Complexity Classes topic works in a narrower field: among problems whose answer **can** be found, it asks how the cost of finding it grows with the input. The first question is this: what makes a problem cheap, and is cheapness a property of the problem or of the chosen method. This lesson runs three decision problems on the same input with the same budget. Two of them barely strain the budget; the third requires the budget to grow. What is measured is not which one is "fast," but **which one the budget decides**. - **CC1.** Every problem in this topic is a **decision problem**: the answer is a single word, "yes" or "no." The concept of a decision problem was established in the Advanced Algorithms course and is not repeated here. - **CC2.** Input size **n** is the number of values in an example. The values are kept between 3 and 99, so a value's digit count is fixed, and input size varies only with n. - **CC3.** The measure is **steps**, not time. What a step is is defined separately for each method, and that definition does not change over the course of the lesson. - **CC4.** The **budget** is a step budget. If a method exhausts the budget, it gives no answer; it returns "undecided." This does not mean there is no answer — it means one **could not be established within this budget**. - **CC5.** Examples come from the shared definition's generator: seed **20260218**, 20 examples, **12 numbers** per example. This course has **no second seed**; instead it has budget sweeps. - **CC6.** The three problems: **Threshold** — does the sum of the numbers exceed the target. **Pair** — do two numbers sum exactly to the target. **Subset sum** — does some subset sum exactly to the target. - **CC7.** A **budget sweep is mandatory.** Every result is shown at at least three budget values, and whether it changes with the budget is stated. - **CC8.** A method's **observed** steps and its **worst-case** steps are written separately. Conflating the two erases the difference this lesson measures. - **CC9.** Whether a problem belongs to class P is **not measured**. The only thing measured is how a specific method's step count grows with input size. - **CC10.** Constant factors are **not dropped**. The measure is not asymptotic; it is the counted step. #### The Decision Problem Class and the Growth Class The Algorithms course's lesson "Reading Complexity Classes" also used the term "complexity class," but it named a different thing. The difference fits in one sentence: there, a class groups a single method's cost expression — $O(n^2)$ is the growth shape of two nested loops — here, a class groups **problems** for which a method is being sought. The distinction's practical consequence is this. A method always belongs to a growth class; this is determined by looking at the code. A **problem**, on the other hand, can only be placed into a decision problem class by showing that "such a method exists," and this is an **existence claim**. Code is measured; an existence claim is not. **P** is a decision problem class: problems for which there exists a deterministic method that gives an **exact** answer in a number of steps bounded by a polynomial in the input size. All three words in the definition carry weight. "Polynomial" is a growth bound; "exact" excludes approximate solutions; "exists" is an existence claim and cannot be established by a single run. #### Three Decision Problems, One Step Budget The block below runs the three problems on the same 20 examples. Each method takes a step budget and, once the budget is exhausted, returns `None` to signal it could not decide. ```python SEED = 20260218 def examples(seed=SEED, n=12, count=20): """Shared definition's example generator: each example is n numbers and a target.""" 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 threshold(numbers, target, budget): """Does the sum exceed the target. One step = one addition.""" total, steps = 0, 0 for s in numbers: if steps >= budget: return None, steps total += s steps += 1 return total > target, steps def pair(numbers, target, budget): """Do two numbers sum to the target. One step = one pair.""" steps, n = 0, len(numbers) for i in range(n): for j in range(i + 1, n): if steps >= budget: return None, steps steps += 1 if numbers[i] + numbers[j] == target: return True, steps return False, steps def subset_sum(numbers, target, budget): """Does some subset sum to the target. One step = one subset.""" steps, n = 0, len(numbers) for mask in range(1 << n): if steps >= budget: return None, steps steps += 1 if sum(numbers[i] for i in range(n) if mask >> i & 1) == target: return True, steps return False, steps EX = examples() print("budget method decided undecided most steps") for b in (12, 100, 1000, 10000): for name, f in (("threshold ", threshold), ("pair ", pair), ("subset sum", subset_sum)): answered = highest = 0 for o in EX: y, a = f(o["numbers"], o["target"], b) if y is not None: answered += 1 highest = max(highest, a) print(f"{b:5d} {name} {answered:15d} {20 - answered:11d} {highest:11d}") ``` ``` budget method decided undecided most steps 12 threshold 20 0 12 12 pair 0 20 0 12 subset sum 0 20 0 100 threshold 20 0 12 100 pair 20 0 66 100 subset sum 7 13 98 1000 threshold 20 0 12 1000 pair 20 0 66 1000 subset sum 19 1 354 10000 threshold 20 0 12 10000 pair 20 0 66 10000 subset sum 20 0 1047 ``` #### What the Budget Answers, What It Cannot Three numbers stand side by side. **Budget 12**: the threshold problem decides 20 of 20 examples, the other two problems decide **none**. **Budget 100**: the pair problem also reaches 20 of 20 and spends at most 66 steps; subset sum stays at **7 examples**, 13 remain undecided. **Budget 10,000**: all three reach 20 of 20. Reading the budget sweep gives two separate results here. For the threshold and pair problems, raising the budget from 100 to 10,000 **changes nothing**: the maximum steps stay fixed at 12 and 66, because these two methods have already exhausted the input. For subset sum, raising the budget **changes everything**: 7, then 19, then 20. This course's second claim shows up twice in a single table. The meaning of the numbers that stay fixed matters more than the ones that don't. The threshold method's 12 steps come from there being 12 numbers in the input; the pair method's 66 steps come from 12 numbers having 66 pairs. Both are numbers readable from the input itself and can be written down beforehand without looking at the example. Subset sum's steps of 98, 354, and 1047, by contrast, cannot be written beforehand; which mask it stops on depends on the example. #### As Input Size Grows A result taken at one budget value may not hold up when input size changes. The second sweep raises input size from 8 to 20 and places each method's worst-case step count next to the highest observed step count. ```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_first(numbers, target): """All subsets; stops at the first match. 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 print(" n threshold pair subset sum (worst case) subset sum (observed max)") for n in (8, 12, 16, 20): highest = max(subset_sum_first(o["numbers"], o["target"])[1] for o in examples(n=n)) print(f"{n:2d} {n:9d} {n * (n - 1) // 2:5d} {1 << n:23d} {highest:26d}") ``` ``` n threshold pair subset sum (worst case) subset sum (observed max) 8 8 28 256 256 12 12 66 4096 1047 16 16 120 65536 945 20 20 190 1048576 2684 ``` The threshold column is 8, 12, 16, 20 — one-to-one with input size. The pair column is 28, 66, 120, 190; as input size rises two and a half times, steps rise roughly sevenfold, that is, **quadratic growth**. The subset column's worst case goes from 256 to **1,048,576**: every new number doubles the count of subsets to be scanned. The last column exposes a trap. The highest **observed** step count is 1047 at 12 numbers, 945 at 16, 2684 at 20. That is, the observed value does not rise steadily with input size — it even drops going from 12 to 16. The reason is that the method stops at the first matching subset; in these examples, a matching subset happens to be found early. In the row for eight numbers, the observed value **coincides** with the worst case — 256 against 256 — because that batch contains an example where no subset matches at all, and there the scan runs to the very end. The rule that follows is this: **an observed step count is not a method's cost.** The highest observed value being 2684 over twenty examples does not say the twenty-first example will finish in 2684 steps. Writing down a method's cost means writing a bound that holds for **every** input, not an observed number. #### What Input Size Is Measured In The "polynomial" in the definition of P is a polynomial **of input size**. What input size actually is is therefore part of the definition, and carelessness at this point turns into a silent error. For subset sum there is another method besides exhaustive search: a table of reachable sums is kept, and every number updates the table once. This method spends **n times target** steps, that is, about 2160 steps for 12 numbers and a target of 180 — below 4096. On the face of it, this is a polynomial method. The block below tests this appearance. All numbers and the target are scaled by the same factor; **the count of numbers stays the same**, only each number's digit count grows. ```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 dp(numbers, target): """Reachable-sum table. One step = one table cell.""" reached = [False] * (target + 1) reached[0] = True steps = 0 for s in numbers: for t in range(target, s - 1, -1): steps += 1 if reached[t - s]: reached[t] = True return reached[target], steps print("factor digits agree brute-force steps dp steps") for c in (1, 10, 100): agree, bfs, dps = 0, 0, 0 digits = 0 for o in examples(): s = [x * c for x in o["numbers"]] h = o["target"] * c digits = max(digits, len(str(h))) y1, a1 = brute_force(s, h) y2, a2 = dp(s, h) agree += y1 == y2 bfs, dps = bfs + a1, dps + a2 print(f"{c:6d} {digits:6d} {agree:5d} {bfs:17d} {dps:9d}") ``` ``` factor digits agree brute-force steps dp steps 1 3 20 4321 37994 10 4 20 4321 377780 100 5 20 4321 3775640 ``` The two methods give the same answer on all 20 examples, so the table method works correctly. But the step columns move in opposite directions. When the numbers are scaled tenfold, exhaustive search's steps stay **fixed at 4321**; the table method's steps rise from 37,994 to 377,780, then to 3,775,640. What was added to the input is a **single digit**, and the count of numbers never changed. The conclusion is this: the table method is a polynomial in the target's **value**, not in the number of digits needed to write the target. The space needed to write a number is proportional to its digit count, not its value; this is why input size grows **exponentially** for this method. If input size is read as "count of numbers," the method looks polynomial; if read as "count of digits written," it does not. This lesson defined input size with fixed digit count in CC2, so the first row is honest; once the factor is scaled up, that definition breaks, and the table immediately shows it. #### What Class P Says, What It Does Not Say The two tables above do **not** place the threshold and pair problems in class P. What places them there is not measurement but the **structure of the method**: the threshold method spends exactly n steps on every input, the pair method spends at most n(n-1)/2, and both bounds can be shown without looking at the input. Measurement **tests** this showing; it does not substitute for it. The reverse direction is even stricter. Subset sum requiring 1,048,576 steps at 20 numbers does **not** show that this problem is outside class P. All it shows is that the method built here spends that many steps. Whether another method exists for the same problem was not measured; it was not built in this lesson at all. This course's rule ties this to a single sentence: **an "unsolvable" claim with no stated budget counts as unmeasured.** The engineering counterpart is direct. In a report, the sentence "this problem is solved in polynomial time" needs **that polynomial** and a bound argument alongside it. The sentence "our method finishes in 66 steps on 20 examples" is measured, true, and a much weaker claim. The two are not written in the same sentence. #### Summary - The decision problem class and the growth class are separate things: one groups problems, the other groups a single method's cost expression. - On the same 20 examples the threshold problem is decided in 12 steps, the pair problem in 66; subset sum decides only 7 of 20 examples at a budget of 100 and completes at 10,000. - Raising the budget from 100 to 10,000 changes nothing for the first two problems, and carries the answered example count from 7 to 20 for the third. - As input size rises from 8 to 20, worst-case step counts go from 8 to 20, from 28 to 190, and from 256 to 1,048,576. - An observed step count is not a method's cost: 1047 is observed at 12 numbers but 945 at 16, because the method stops at the first matching subset. - A problem belonging to class P is not shown by measurement; measurement only tests a bound that has already been shown. #### Next Step In the subset sum problem, the scan was expensive, but once the scan finished, one more thing remained: the subset that summed to the target itself. Once that subset is obtained, checking that it is correct does not require redoing the scan. The next lesson turns this observation into a measure: how large is the step gap between **finding** an answer and **verifying** a given one, and what does it mean for this gap to have a class name. ### Class NP Source: https://academia.sh/en/courses/theory-of-computation/class-np Establishing verifiability and the certificate concept in step counts: on 20 examples, solving spends 4321 steps, certificate verification 101, a ratio of 42.8. At a step budget of 13, 20 of 20 examples are decided with a certificate, while solving decides none. At input size 24, solving's worst case is 16,777,216 steps, verification 25. A certificate with one index dropped is rejected on 20 of 20 examples. The difference between this course's sense of "certificate" and the digital certificate sense in the Cryptography curriculum is stated separately. The previous lesson scanned the subset sum problem up to 1047 steps at 12 numbers, and once the scan finished, one more thing remained: the subset that summed to the target itself. Once that subset is written down, checking its correctness does not require redoing the scan; a few additions suffice. This lesson turns that observation into a measure. The difference measured is not a difference in speed; it is **two separate costs for two separate questions**. The first question: does some subset sum to the target. The second question: does **this given** subset sum to the target. The method answering the second question performs no search at all; it only looks. - **CC11.** A **certificate** is a witness that makes a "yes" answer verifiable. Here it is a list of indices: which numbers were taken. - **CC12.** The **verifier** is the method that takes a certificate and tests the "yes" answer. A verifier **does not search**; this is this lesson's strictest constraint. A verifier that searches is a solver. - **CC13.** For the verifier, a step is **reading one index**; the final comparison also counts as a step. For the solver, a step is **one subset**. - **CC14.** The certificate's **length** is measured. A certificate that does not stay proportional to input size does not make verification cheap. - **CC15.** The verifier is tested not only by acceptance but also by **rejection**: what it says when given a corrupted certificate is counted. - **CC16.** A certificate is not defined for a "no" answer. This lesson measures only the **yes** direction; the other direction belongs to lesson `04`. - **CC17.** The budget sweep is done at four values: 13, 100, 1000, 10,000 steps. - **CC18.** Examples come from the shared definition's generator: seed **20260218**, 20 examples, 12 numbers per example. There is no second seed. - **CC19.** Whether a problem belongs to class NP is **not measured**. What is measured is how many steps a specific verifier takes to test a specific certificate. #### In Which Sense "Certificate" Is Used The same word also appears in the Cryptography curriculum, where it names a different thing. The difference fits in one sentence: there, a certificate is a **signed document that binds an identity to a public key**; here, a certificate is a **witness that makes a decision problem's "yes" answer testable in a short number of steps**. The only thing the two share is that both can be **verified without being produced by the verifier**; beyond that they have no relation and are not used in the same sentence. **NP** is a decision problem class: problems whose "yes" answer can be verified with a certificate whose length is a polynomial in input size, and in a polynomial number of steps. The definition contains no mention of "solving." This is why NP does **not** mean "not solvable in polynomial time"; the expansion of the name does not say that either. Every problem in class P is in class NP: if a method exists that can solve a problem in polynomial steps, the verifier can solve the problem from scratch without ever reading the certificate and give the answer. Whether the reverse direction holds is the subject of this course's lesson `05`, and it is **open**. #### Solving Versus Verifying The block below runs the solver on every example first, takes the certificate it produces, and gives it to the verifier. Then the same certificate, with one index dropped, is given to the verifier again. ```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 solver(numbers, target): """All subsets are scanned. Returns: (exists, steps, certificate).""" 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, [i for i in range(n) if mask >> i & 1] return False, steps, None def verifier(numbers, target, certificate): """Verifies the given certificate; performs no search at all. One step = one index read.""" steps, total = 0, 0 for i in certificate: steps += 1 total += numbers[i] return total == target, steps + 1 LOG = [] for o in examples(): exists, steps, cert = solver(o["numbers"], o["target"]) ok, vs = verifier(o["numbers"], o["target"], cert) LOG.append({"example": o, "exists": exists, "solve": steps, "certificate": cert, "verify": vs, "valid": ok}) ts = sum(k["solve"] for k in LOG) tv = sum(k["verify"] for k in LOG) print("20 examples, n=12 | yes answer:", sum(1 for k in LOG if k["exists"]), "/ 20") print(" verifier confirmed certificate:", sum(1 for k in LOG if k["valid"]), "/ 20") print(" solve steps:", ts, "| verify steps:", tv, "| ratio:", round(ts / tv, 1)) print(" longest certificate:", max(len(k["certificate"]) for k in LOG), "indices") print() print("budget established solving established with certificate") for b in (13, 100, 1000, 10000): c1 = sum(1 for k in LOG if k["solve"] <= b) c2 = sum(1 for k in LOG if k["verify"] <= b) print(f"{b:5d} {c1:14d} {c2:21d}") print() rejected, ra = 0, 0 for k in LOG: s = k["certificate"] trimmed = s[:-1] if len(s) > 1 else s + [0] ok, a = verifier(k["example"]["numbers"], k["example"]["target"], trimmed) ra += a rejected += not ok print("certificate with one index dropped | rejected:", rejected, "/ 20", "| total steps:", ra) ``` ``` 20 examples, n=12 | yes answer: 20 / 20 verifier confirmed certificate: 20 / 20 solve steps: 4321 | verify steps: 101 | ratio: 42.8 longest certificate: 5 indices budget established solving established with certificate 13 0 20 100 7 20 1000 19 20 10000 20 20 certificate with one index dropped | rejected: 20 / 20 | total steps: 81 ``` #### Reading the Three Numbers **Budget 13**: with a certificate, 20 of 20 examples are decided; by solving, **none**. At budget 100, solving rises to 7, at 1000 to 19, at 10,000 to 20. The certificate column, meanwhile, **never changes**: it was already full at the smallest budget, and growing it found nothing to add. This is the cleanest view of this course's second claim — raising the budget changes everything in one column and nothing in the other. The totals say the same thing: solving **4321**, verification **101** steps, a ratio of **42.8**. The certificate's length is at most **5 indices**; the input has 12 numbers, so the certificate is shorter than the input. Measuring the length is not a formal nicety: the verifier's step count depends on the certificate's length, and if a certificate longer than the input were allowed, verification's cheapness would vanish on its own. The fourth number shows how serious the verifier is. When one index is dropped from the certificate, the verifier rejects it on **20 of 20** examples, doing so in a total of **81 steps**. Rejecting is no more expensive than accepting, but no cheaper either; the verifier only looks either way. Without this measurement, the sentence "verification is cheap" would stay incomplete: a method that approves every certificate is also cheap, and useless. #### Why the Certificate's Shortness Is Part of the Definition The definition of NP requires the certificate to be **polynomial in length**. If this condition is dropped, the definition becomes empty, and this can be measured. The block below places three separate certificate designs for the same problem side by side: an index list, only the word "yes," and the list of all subset sums. ```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 short_certificate(numbers, target): """Index list. Length at most n.""" n = len(numbers) for mask in range(1 << n): if sum(numbers[i] for i in range(n) if mask >> i & 1) == target: return [i for i in range(n) if mask >> i & 1] return [] def short_verifier(numbers, target, certificate): steps, total = 0, 0 for i in certificate: steps += 1 total += numbers[i] return total == target, steps + 1 def empty_verifier(numbers, target, certificate): """Certificate is only the word 'yes'; the verifier is forced to search.""" 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 long_certificate(numbers, target): """All subset sums are written out in order. Length 2^n.""" n = len(numbers) return [sum(numbers[i] for i in range(n) if m >> i & 1) for m in range(1 << n)] def long_verifier(numbers, target, certificate): steps = 0 for t in certificate: steps += 1 if t == target: return True, steps return False, steps EX = examples() print("certificate length verifier steps budget 13 budget 100 budget 10000") for name, produce, vf in (("index list ", short_certificate, short_verifier), ("only 'yes' ", lambda s, h: [], empty_verifier), ("all sums ", long_certificate, long_verifier)): length = va = 0 b13 = b100 = b1e4 = 0 for o in EX: cert = produce(o["numbers"], o["target"]) ok, a = vf(o["numbers"], o["target"], cert) length += len(cert) va += a b13 += a <= 13 b100 += a <= 100 b1e4 += a <= 10000 print(f"{name:15s} {length:7d} {va:11d} {b13:8d} {b100:9d} {b1e4:11d}") ``` ``` certificate length verifier steps budget 13 budget 100 budget 10000 index list 81 101 20 20 20 only 'yes' 0 4321 0 7 20 all sums 81920 4321 0 7 20 ``` The three rows produce the same answer but do three separate jobs. In the first row, total certificate length is **81 indices** and the verifier spends **101 steps**. In the second row the certificate is empty: since the verifier receives no witness at all, it is forced to search from scratch and spends **4321 steps**; this is not a verifier, it is a solver. The third row is sneakier. There **is** a certificate, in fact a lot of one — **81,920 numbers** in total, that is, 4096 per example — and the verifier really does only read, not search. But because what it reads is exponentially longer than the input, the step count is again **4321**. The budget columns close the gap: at budget 13 only the first design gives 20 of 20, the others stay at zero. Without the length bound, a "verifiable" design could be built for every problem, and NP would contain every decision problem. **The shortness condition in the definition is what keeps the definition from being empty.** The Advanced Algorithms course had already measured this difference on another problem: in the Hamiltonian path lesson, verifying a candidate path cost 7 steps per graph, finding a path cost 61 on average, and at twelve nodes verification cost 11 steps while showing that no path existed rose to an average of 11,601. That lesson measured the difference and left the naming to here; its name is **verifiability**, its class is **NP**. #### What the Gap Does with Input Size The 42.8 ratio over twenty examples is a number taken at a single input size. The second sweep varies input size and places both sides' worst-case steps side by side. This table runs no examples at all; it computes the two numbers directly, since both can be written without looking at the input. ```python print(" n solve (worst case) verify (worst case) ratio") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {1 << n:15d} {n + 1:19d} {(1 << n) // (n + 1):9d}") ``` ``` n solve (worst case) verify (worst case) ratio 8 256 9 28 12 4096 13 315 16 65536 17 3855 20 1048576 21 49932 24 16777216 25 671088 ``` The left column doubles at every row: 256, 4096, 65,536, 1,048,576, 16,777,216. The middle column rises by one each time: 9, 13, 17, 21, 25. The ratio climbs from 28 to **671,088**. As input size triples, the gap grows twenty-four-thousandfold. The table's left column carries a warning. The number 16,777,216 is not this problem's cost; it is **this solver's** cost. Whether a method spending fewer steps exists for the same problem was not measured here. The only thing measured is how many subsets exhaustive search sees at 24 numbers. The right column, by contrast, sits closer to the problem itself: given a certificate, **n+1** steps suffice, and this bound is independent of which method is chosen. #### What Verifiability Does Not Promise A problem being in class NP does **not** say the problem is cheap. NP only says this: if the correct answer is "yes," there **exists** a short witness that shows it to you. It says nothing about how to find that witness, and this lesson measured that finding it took 4321 steps. The distinction finds a direct engineering counterpart. In a system, testing that a layout plan, a schedule, or a configuration is **valid** is often cheap and measurable. **Producing** that same plan is an entirely different job. Unless a report writes "verification: 13 steps" next to "production: 4096 steps," the sentence "the system validates the plan" does not say which job was done. The class name itself carries a warning. NP is short for "nondeterministic polynomial time," and the nondeterminism here corresponds not to a machine design but to **the witness being treated as given**. Reading the class name as "not polynomial" is a common mistake, and it inverts every number this lesson measured: the threshold problem, which is in class P, is also in class NP, because the verifier constructs the answer in 13 steps without ever looking at a certificate. One final limit: no number measured in this lesson **proves** that subset sum is in class NP. What proves it is the **structure of the verifier** — the certificate carries at most n indices, and the verifier spends at most n+1 steps, on every input. Measurement tested this structure and found it consistent across 20 examples; this is a test, not a substitute for proof. #### Summary - A certificate is a witness that makes a "yes" answer testable without searching; the verifier reads the certificate, it does not search. - On the same 20 examples, solving spends 4321 steps, verification 101, a ratio of 42.8; the longest certificate is 5 indices, the input is 12 numbers. - At a step budget of 13, 20 of 20 examples are decided with a certificate, none by solving; raising the budget to 10,000 changes nothing in the certificate column. - A certificate with one index dropped is rejected on 20 of 20 examples; the verifier is tested by rejection as much as by acceptance. - As input size rises from 8 to 24, the worst case for solving goes from 256 to 16,777,216, verification from 9 to 25, and the ratio climbs to 671,088. - Being in class NP promises no cheapness; it only says a "yes" answer has a short witness, and it says nothing about how to find that witness. #### Next Step This 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. The next lesson counts how this comparison is built: how many steps the transformation that translates one problem into another takes, whether the transformation preserves the answer, and why translation **carries** difficulty but does not **reduce** it. ### NP-Complete and NP-Hard Source: https://academia.sh/en/courses/theory-of-computation/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. ### co-NP and Relationships Between Classes Source: https://academia.sh/en/courses/theory-of-computation/co-np-and-relationships-between-classes The status of complement problems and the measured asymmetry between yes and no answers: on 20 examples, a yes certificate closes in 101 steps, while a no answer by exhaustive search needs 81,920. On structured no examples, a short 260-step proof works on 20 of 20; on unstructured examples, the same proof can say nothing on 20 of 20. At input size 24, the yes certificate takes 25 steps, the no proof 16,777,216. The threshold problem closes in 260 steps in both directions. Everything measured up to this point pointed in the yes direction: a certificate verified a "yes"; a reduction carried a "yes." When an answer is "no," what can be shown? This lesson measures the missing direction and counts that the two directions are **not symmetric**. The source of the problem is the definition of NP itself. The definition demands a witness only for a "yes" answer; it promises nothing for a "no" answer. The Advanced Algorithms course had already observed this asymmetry in the Hamiltonian path lesson: on **every** graph with no path, the decision method traversed the entire tree the counting method traversed. That observation turns into a class distinction here. - **CC29.** A decision problem's **complement** is the problem with the answer flipped on the same input: the complement of "does some subset sum to the target" is "does **no** subset sum to the target." - **CC30.** **co-NP** is the class of decision problems whose complement is in class NP. An equivalent reading: problems for which the "no" answer has a **short, quickly testable witness**. - **CC31.** Three example sets are built. **Yes set:** the shared definition's 20 examples. **Structured no set:** all numbers are doubled, the target is made odd. **Unstructured no set:** the same numbers, with an unreachable value chosen as the target. - **CC32.** Choosing the unstructured set's target requires working out reachable sums exactly. This is a **setup step**, not a verifier, and its steps are not included in the measurement. - **CC33.** The **short no proof** tests only a necessary condition: if all numbers are even, their sum is even too, so an odd target cannot be reached. This proof can say "no"; it cannot say "yes." When it cannot decide, it returns **unknown**. - **CC34.** For the short proof, a step is **reading one number**; for exhaustive search, it is **one subset**. - **CC35.** The budget sweep is done at four values: 13, 100, 1000, 10,000 steps. - **CC36.** Examples come from the shared definition's generator, seed **20260218**. There is no second seed. - **CC37.** Whether NP equals co-NP is an **open question** and is not answered in this lesson. Measurement only counts whether specific proofs work on specific examples. #### Why the Complement Is a Separate Question A method that solves a decision problem also solves its complement: flipping the answer does not even cost a step. This is why, in terms of **solvability**, there is no difference between a problem and its complement, and class P is **closed under complement** — the complement of a problem in P is also in P. The situation is different in terms of **verifiability**. A witness saying "this subset sums to the target" does not support the claim "no subset sums to it" — on the contrary, it refutes that claim. What should be shown to say "none does" is a separate design question, and it is not known whether every problem has an answer to it. This is why NP and co-NP carry separate names. Subset sum being in class NP was shown in `02`; whether it is in class co-NP was **not** shown, and this lesson does not show it either. #### Measuring the Two Directions The block below runs all three example sets through the same verifier, then tries two separate short proofs on each set: a certificate for "yes," an even/odd necessary condition for "no." ```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 verifier(numbers, target): """Exhaustive search. Returns: (exists, steps, certificate).""" 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, [i for i in range(n) if mask >> i & 1] return False, steps, None def yes_verify(numbers, target, certificate): """One step = one index read.""" steps, total = 0, 0 for i in certificate: steps += 1 total += numbers[i] return total == target, steps + 1 def no_verify(numbers, target): """One-directional short proof: if all numbers are even, their sum is even too, so an odd target can never be reached.""" steps = 0 for s in numbers: steps += 1 if s % 2: return "unknown", steps steps += 1 return ("no", steps) if target % 2 else ("unknown", steps) def unreachable(numbers): """Setup step (not a verifier): reachable sums are worked out and the unreached value closest to a third of the total is chosen.""" 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] STRUCTURED = [([2 * x for x in o["numbers"]], 2 * o["target"] + 1) for o in EX] UNSTRUCTURED = [(o["numbers"], unreachable(o["numbers"])) for o in EX] print("set verifier answer exhaustive search steps") for name, batch, expect in (("yes ", YES, True), ("structured ", STRUCTURED, False), ("unstructured", UNSTRUCTURED, False)): total = sum(verifier(s, h)[1] for s, h in batch) matched = sum(1 for s, h in batch if verifier(s, h)[0] == expect) print(f"{name} {matched:2d}/20 expected {total:16d}") print() es = sum(yes_verify(s, h, verifier(s, h)[2])[1] for s, h in YES) print("yes certificate (20 examples) verification steps:", es) for name, batch in (("structured ", STRUCTURED), ("unstructured", UNSTRUCTURED)): hy = sum(1 for s, h in batch if no_verify(s, h)[0] == "no") ha = sum(no_verify(s, h)[1] for s, h in batch) print(f"short no proof {name} | said 'no': {hy:2d}/20 | steps: {ha}") print() print("budget yes certificate structured no proof unstructured exhaustive search") for b in (13, 100, 1000, 10000): a1 = sum(1 for s, h in YES if yes_verify(s, h, verifier(s, h)[2])[1] <= b) a2 = sum(1 for s, h in STRUCTURED if no_verify(s, h)[0] == "no" and no_verify(s, h)[1] <= b) a3 = sum(1 for s, h in UNSTRUCTURED if verifier(s, h)[1] <= b) print(f"{b:5d} {a1:16d} {a2:19d} {a3:19d}") ``` ``` set verifier answer exhaustive search steps yes 20/20 expected 4321 structured 20/20 expected 81920 unstructured 20/20 expected 81920 yes certificate (20 examples) verification steps: 101 short no proof structured | said 'no': 20/20 | steps: 260 short no proof unstructured | said 'no': 0/20 | steps: 39 budget yes certificate structured no proof unstructured exhaustive search 13 20 20 0 100 20 20 0 1000 20 20 0 10000 20 20 20 ``` #### Reading the Asymmetry The first table establishes the asymmetry all by itself. On the yes set, exhaustive search spends **4321 steps**, because it stops once a matching subset is found. On the two no sets it spends **81,920 steps** — exactly 4096 per example, no discount at all. The number is identical across the two sets because the reason is not procedural but **logical**: to say "none does," not a single unseen subset can remain. The second block brings three numbers together. **Yes certificate: 101 steps.** **Structured no proof: 260 steps**, and it can say "no" on **20 of 20** examples. **Unstructured no proof: 39 steps**, and it can say nothing on **none** of the 20 examples — it backs off the moment it sees the first odd number. This trio shows why the definition of co-NP is an existence claim. A short "no" witness **exists** for some examples, and it was measured: 13 steps instead of 4096. But its existing for **every** example is a separate claim, and the unstructured set shows this claim does not hold automatically. What the measurement says is: **this proof did not work on these examples.** What it does not say is that no other short proof exists; no such proof was searched for — only this one was tried. The budget sweep gives the same distinction once more. The yes certificate and the structured no proof are **full at budget 13**; raising the budget a thousandfold changes nothing in either. The unstructured set, meanwhile, is **still zero at 1000** and only reaches 20 at 10,000. #### A Problem Where Both Directions Are Cheap Not every problem has this asymmetry. The threshold problem — does the sum of the numbers exceed the target — closes with the same method in both directions: the total is computed once and compared. ```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 threshold(numbers, target): """Does the sum exceed the target. Both directions close with the same method.""" total, steps = 0, 0 for s in numbers: total += s steps += 1 return total > target, steps + 1 yes = no = ya = na = 0 for o in examples(): y1, a1 = threshold(o["numbers"], o["target"]) y2, a2 = threshold(o["numbers"], sum(o["numbers"]) + 1) yes, no = yes + y1, no + (not y2) ya, na = ya + a1, na + a2 print("threshold problem | yes:", yes, "/20 ,", ya, "steps | no:", no, "/20 ,", na, "steps") print() print(" n yes certificate no proof (exhaustive search)") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {n + 1:16d} {1 << n:25d}") ``` ``` threshold problem | yes: 20 /20 , 260 steps | no: 20 /20 , 260 steps n yes certificate no proof (exhaustive search) 8 9 256 12 13 4096 16 17 65536 20 21 1048576 24 25 16777216 ``` In the threshold problem, both directions take **260 steps**: identical, and the equality is not a coincidence but comes from the method's structure. This problem is in both class NP and class co-NP, because it is in class P, and P sits inside both classes. The direction of the answer does not change the cost. The table below it is the opposite extreme. As input size rises from 8 to 24, the yes certificate goes from 9 to 25 steps, the no proof from 256 to **16,777,216**. The two columns are two faces of the same problem, and they do not grow at the same speed. #### The Same No, Fewer Steps Exhaustive search spending 81,920 steps on the unstructured set is not the cost of saying "no" for those examples; it is only the cost of **exhaustive search**. The way to show this is to try another method that establishes the same answer in fewer steps. The block below tries two: a **pruned search** that cuts a branch once the partial sum exceeds the target, and the reachable-sum table introduced in `01`. ```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 unreachable(numbers): 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)) 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 pruned(numbers, target): """A branch is cut once the partial sum exceeds the target. One step = one node.""" s = sorted(numbers) n, steps = len(s), 0 def visit(i, total): nonlocal steps steps += 1 if total == target: return True if total > target or i == n: return False return visit(i + 1, total + s[i]) or visit(i + 1, total) return visit(0, 0), steps def dp(numbers, target): """Reachable-sum table. One step = one table cell.""" reached = [False] * (target + 1) reached[0] = True steps = 0 for x in numbers: for t in range(target, x - 1, -1): steps += 1 if reached[t - x]: reached[t] = True return reached[target], steps UNSTRUCTURED = [(o["numbers"], unreachable(o["numbers"])) for o in examples()] print("method says no total steps budget 1000 budget 10000") for name, f in (("exhaustive search", brute_force), ("pruned search ", pruned), ("dp table ", dp)): hy = top = b3 = b4 = 0 for s, h in UNSTRUCTURED: y, a = f(s, h) hy += not y top += a b3 += a <= 1000 b4 += a <= 10000 print(f"{name:15s} {hy:11d} {top:11d} {b3:10d} {b4:11d}") ``` ``` method says no total steps budget 1000 budget 10000 exhaustive search 20 81920 0 20 pruned search 20 21594 12 20 dp table 20 15736 16 20 ``` All three methods say "no" on 20 of 20 examples, so all three establish the same answer. Their step counts, though, are **81,920**, **21,594**, and **15,736**: pruned search spends slightly more than a quarter of exhaustive search, the table method less than a fifth. At budget 1000, exhaustive search stays at zero, pruned search decides 12 examples, and the table method 16. One section ago it was said "this proof did not work on these examples"; now the same examples close four to five times cheaper. Even so, closing did not fall to n+1 steps, and the table method's cheapness, as seen in `01`, depends on the value of the target. The conclusion fits two sentences: **the best number measured is not the best number that could be measured**; and finding a better number is not the same thing as proving a bound. #### What Is Known and What Is Open What is known is short. **Class P sits inside both NP and co-NP**, and is closed under complement. **It is not known whether an NP-complete problem's complement is in class NP.** If a problem is in both NP and co-NP, it means it has a short witness in **both** directions; this is a strong property, and not every problem has it. What is open is also short: **it is not known whether NP equals co-NP.** This lesson does not answer that question and does not try to. What it measures is whether a single short proof works on 20 examples or does not. The proof giving 0/20 on the unstructured set does not show that no short proof exists for those examples; it only shows that **this** proof does not fit them. This distinction is a direct application of the course's ban on overclaiming. The engineering counterpart is concrete. In a validator, justifying a "valid" answer and justifying an "invalid" one are two separate jobs: the first can show a witness, the second often has to say "I have seen every possibility." Unless the two directions' step counts are written down separately, the validator's cost does not count as known. #### Summary - A problem's complement is indistinguishable from it in terms of solvability; in terms of verifiability it is a separate question, because a certificate cannot be flipped and reused. - On the yes set, exhaustive search spends 4321 steps; on both no sets, 81,920 — 4096 per example, no discount at all. - The short no proof works on 20 of 20 structured examples and takes 260 steps; it says nothing on any of the unstructured examples and backs off in 39 steps. - In the threshold problem both directions close in 260 steps; because this problem is in class P, it is in both NP and co-NP. - As input size rises from 8 to 24, the yes certificate goes from 9 to 25 steps, the no proof from 256 to 16,777,216. - Whether NP equals co-NP is an open question; a proof not working on these examples does not show that no short proof exists. #### Next Step With this lesson, four class names and the known relationships between them are established. What remains is the most talked-about, least answered question: is everything verifiable also solvable. The next lesson states this question and does not try to measure what it cannot measure. The only thing it can measure is the gap between the best known method and the best known lower bound; whether that gap can be narrowed, whether narrowing it closes it, and whether the narrowing itself can be counted as a sign of direction. ### The P vs NP Question Source: https://academia.sh/en/courses/theory-of-computation/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 a millionfold, exhaustive search's reach goes from 13 to 33: the budget grows a million times over, 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. ### Approximation and Heuristic Methods Source: https://academia.sh/en/courses/theory-of-computation/approximation-and-heuristic-methods Counting the cost of giving up an exact solution, and the course's closing: the greedy approximation finds the exact result on 5 of 20 examples, diverges on 15, with a worst relative loss of 0.0676. As the exhaustively searched element count rises from 0 to 8, diverging examples drop from 15 to 0 and steps rise from 240 to 35,956; at k=12 the method spends 553,948 steps, exceeding the oracle's 81,920. The course closing carries a ten-row budget table and the closing of the Computer Science curriculum. The previous lesson left three paths and left the third one open: giving up on an exact solution. This lesson counts that path's 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 given budget is grown, does the loss really close. The problem measured is again subset sum, but its question changes. In the decision form, the question was "does some subset reach the target exactly." In the **optimization form**, the question is: **what is the largest subset sum not exceeding the target.** This form makes room for approximation, because now an answer can be **short**, not "wrong." - **CC48.** The **oracle** is exhaustive search: the largest sum not exceeding the target, found by seeing every subset. The oracle's correctness is **by definition**. - **CC49.** **Relative loss** is the oracle's value minus the approximation's value, divided by the oracle's value. Not the average — the **worst** relative loss is written down. - **CC50.** **Approximation ratio** is a bound **proven** for all inputs. **What this lesson measures is not the approximation ratio — it is the relative loss observed on 20 examples**, and the two are not used in the same sentence. - **CC51.** The approximate method is a **hybrid** method: exhaustive search is done on the largest k elements, and the rest are filled **greedily**. **k = 0** is pure greedy approximation, **k = n** turns into exhaustive search. - **CC52.** The **budget** is the exhaustively searched element count k, and it is swept: 0, 4, 8, 12. - **CC53.** A step is **one element examined**; for the oracle it is **one subset**. - **CC54.** The count of diverging examples and the relative loss are written **separately**. Diverging alone does not say **by how much**. - **CC55.** Examples come from the shared definition's generator: seed **20260218**, 20 examples, 12 numbers per example. There is no second seed. - **CC56.** If loss comes out zero at a budget, this does **not** mean that budget will find the exact result on every input. **Observation is not proof.** - **CC57.** In the input-size sweep, every row is a **separate batch**; rows are not extensions of one another, and no direction is read from a single row. - **CC58.** Loss is **not measured** at an input size where the oracle cannot be run. No number is written for an unmeasured range. #### What Loss Is Measured Against An approximate solution's quality can only be measured if an oracle exists. The Advanced Algorithms course built this method on the traveling salesman problem: the oracle finds the best tour by exact enumeration, and the gap is measured against it. The method is not retold, it is used directly — and the same limit applies here. **Loss cannot be measured on input the oracle cannot run**; all that exists is a generalization made from small input. The second distinction is terminological, and it is strict in this course. **Approximation ratio** is a bound that has been **proven**: it holds for every input and comes from a proof. **Relative loss** is a measured value: it is observed on specific examples. The worst relative loss over twenty examples coming out to 0.0676 does **not** say the approximation ratio is 0.0676; what the twenty-first example would give was not measured. #### The Budget Sweep The block below sweeps the budget given to the approximate method across four values and compares it against the oracle at each one. ```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 oracle(numbers, target): """The largest subset sum not exceeding the target. Exhaustive search.""" n, best, steps = len(numbers), 0, 0 for mask in range(1 << n): steps += 1 t = sum(numbers[i] for i in range(n) if mask >> i & 1) if best < t <= target: best = t return best, steps def hybrid(numbers, target, k): """Exhaustive search on the largest k elements, the rest filled greedily. k=0 is pure greedy, k=n turns into exhaustive search. One step = one element examined.""" s = sorted(numbers, reverse=True) top, rest = s[:k], s[k:] best, steps = 0, 0 for mask in range(1 << k): t, valid = 0, True for i in range(k): steps += 1 if mask >> i & 1: t += top[i] if t > target: valid = False break if not valid: continue for x in rest: steps += 1 if t + x <= target: t += x best = max(best, t) return best, steps EX = examples() print("budget k exact diverge worst relative loss total steps") for k in (0, 4, 8, 12): exact = diverge = top = 0 worst = 0.0 for o in EX: e, _ = oracle(o["numbers"], o["target"]) y, a = hybrid(o["numbers"], o["target"], k) top += a if y == e: exact += 1 else: diverge += 1 worst = max(worst, (e - y) / e) print(f"{k:7d} {exact:9d} {diverge:7d} {round(worst, 4):19} {top:11d}") print() print("oracle (exhaustive search) total steps:", sum(oracle(o["numbers"], o["target"])[1] for o in EX)) ``` ``` budget k exact diverge worst relative loss total steps 0 5 15 0.0676 240 4 15 5 0.0125 2980 8 20 0 0.0 35956 12 20 0 0.0 553948 oracle (exhaustive search) total steps: 81920 ``` #### Reading the Loss Three numbers side by side. **Budget k=0**: pure greedy approximation finds the exact result on **5 of 20** examples, diverges on **15**, worst relative loss **0.0676**, and it does this in **240 steps**. The oracle spends **81,920 steps** for the same job. That is, with **341 times fewer** steps, a loss of under seven percent in the worst case. Growing the budget really does close the loss. **k=4**: diverging examples drop from 15 to **5**, worst loss from 0.0676 to **0.0125**; the cost is 2980 steps instead of 240. **k=8**: diverging examples **0**, loss **0**, cost **35,956 steps**. This is one of the clearest examples in this course of the budget sweep "changing everything." The last row carries a warning. **At k=12 the method spends 553,948 steps** — nearly seven times the oracle's 81,920. A heuristic whose budget has been grown all the way does not just turn into exhaustive search — it turns into an exhaustive search **more expensive than exhaustive search**, since it refills the remaining elements greedily for every mask. **Making an approximate method exact does not produce a good exact method.** The zeros in the k=8 row must also be read carefully. Zero loss was observed **on these 20 examples**. It was **not shown** that exhaustive search over eight elements will find the exact result on every input; the remaining four elements are filled greedily, and there is no argument that this filling will always give the best result. This course's third claim holds one last time here: **observation is not proof.** #### When Input Size Changes The 0.0125 loss in the k=4 row is a number taken at a single input size. The second sweep runs the same budget across three separate input sizes. Every row is a **separate batch**, generated for its own input size; the sixteen-number examples are not an extension of the twelve-number ones. ```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 oracle(numbers, target): n, best, steps = len(numbers), 0, 0 for mask in range(1 << n): steps += 1 t = sum(numbers[i] for i in range(n) if mask >> i & 1) if best < t <= target: best = t return best, steps def hybrid(numbers, target, k): """Exhaustive search on the largest k elements, the rest filled greedily.""" s = sorted(numbers, reverse=True) top, rest = s[:k], s[k:] best, steps = 0, 0 for mask in range(1 << k): t, valid = 0, True for i in range(k): steps += 1 if mask >> i & 1: t += top[i] if t > target: valid = False break if not valid: continue for x in rest: steps += 1 if t + x <= target: t += x best = max(best, t) return best, steps print(" n exact worst relative loss hybrid steps oracle steps") for n in (8, 12, 16): exact, ya, ha = 0, 0, 0 worst = 0.0 for o in examples(n=n): e, a1 = oracle(o["numbers"], o["target"]) y, a2 = hybrid(o["numbers"], o["target"], 4) ha, ya = ha + a1, ya + a2 if y == e: exact += 1 else: worst = max(worst, (e - y) / e) print(f"{n:2d} {exact:9d} {round(worst, 4):19} {ya:14d} {ha:11d}") ``` ``` n exact worst relative loss hybrid steps oracle steps 8 19 0.0109 1620 5120 12 15 0.0125 2980 81920 16 19 0.0037 4690 1310720 ``` The two columns show two separate growth patterns. The approximation's steps are 1620, 2980, 4690: as input size doubles, they grow by less than triple. The oracle's steps go from 5120 to **1,310,720**, that is, **256-fold** — multiplied by sixteen for every four numbers added. At sixteen numbers the oracle spends **279 times** as many steps as the approximation; since the approximation's steps grow too, this ratio goes from 3.2 to 27.5 to 279, that is, roughly tenfold for every four numbers added. The loss column, though, is not regular: 0.0109, 0.0125, 0.0037. The count finding the exact result is also 19, 15, 19. This irregularity is expected, because each row is a separate batch, and no direction can be read from a single row. What **can** be read is smaller and more precise: **across every input size measured, loss stayed under one and a half percent**, and this sentence holds for the range between 8 and 16 numbers. The column on the right also says why this range is narrow. At twenty-four numbers the oracle must see **16,777,216** subsets; there, loss cannot be measured, because the exact result to compare against is not known. Every sentence written about an approximate solution's quality on large input either generalizes from a loss measured on small input, or rests on a proven approximation ratio; this lesson did the former and claims none of the latter. #### What the Heuristic Cannot Know There is one more limit beyond the measured loss, and it has no number. The approximate method **cannot know on its own** that it diverged on a given example. Running k=0 produces a number; whether that number is the oracle's number can only be known by **running the oracle**, and if the oracle can be run, there is no need for the approximation. Knowing that the diverging example count is 15 is not the same as knowing **which** 15 examples they are. The practical consequence of this is as follows. What must be written alongside an approximate solution when it is deployed is not the average loss but the **worst** loss, and the input range in which that loss was measured. In a report, the sentence "runs with one percent loss" says nothing unless the input size and the range in which the oracle could be run are written down with it. #### Summary - In optimization form, an answer can be short rather than wrong; shortness can only be measured with an oracle, and loss cannot be measured on input the oracle cannot run. - Pure greedy approximation finds the exact result on 5 of 20 examples, diverges on 15, with a worst relative loss of 0.0676 at a cost of 240 steps; the oracle spends 81,920 steps. - At budget k=4, diverging examples drop to 5 and loss to 0.0125; at k=8 both drop to 0, at a cost of 2980 and 35,956 steps. - At k=12 the method spends 553,948 steps, exceeding the oracle's 81,920: a heuristic whose budget is grown all the way does not yield a good exact method. - Observing zero loss is not proof that budget will find the exact result on every input; measured relative loss and a proven approximation ratio are separate things. - The approximate method cannot know on its own that it diverged; what must be written when it is deployed is the worst loss and the input range it was measured in. #### Course Wrap-Up The Theory of Computation course followed a single question across ten lessons: what does a finite budget answer, what can it not answer, and does growing the budget change this. The table below gathers each lesson's budget and both sides of that budget. The four rows for the Models of Computation topic are taken from their source lessons; the numbers are not fabricated. | Lesson | Budget | What the budget answers | What it cannot answer | |---|---|---|---| | Finite Automata | states 1–3, universe of 31 strings | 2, 26, and **1054** distinct languages | share of **0.0000004908** next to 2³¹ languages; at k=2, freezes at **26** past length 2 | | Context-Free Languages | states 1–5, length 2–10 | classes **4, 6, 8, 10, 12**; exact count gives smallest k of **5** at length 4 | that no fixed k suffices at **any** length cannot be measured; a one-line rule generates the entire target in three derivation steps | | Turing Machine | steps 1–200, 20,736 machines | **9784** halt, longest run **6** steps | count never changes past budget 6; of the 10,952 that do not halt, **5040** are decided by proof, **5912** remain unknown | | Undecidability | steps 5–200, 1000 starting points | **7, 155, 569, 756, 1000** | at 5000 starting points the same budget fails to decide **9** of them; 1000/1000 halting is not proof | | Class P | step budget 12–10,000 | threshold 20/20 (12 steps), pair 20/20 (66 steps) | subset sum 7/20 at 100 steps; whether the problem is in P | | Class NP | step budget 13–10,000 | with a certificate 20/20, total 101 steps | solving gives 0/20 at 13 steps; how to find the witness | | NP-Complete and NP-Hard | step budget 15–10,000 | reduction 20/20, 300 steps, answer preserved | that partition is NP-complete; that every NP problem reduces to it | | co-NP and Relationships Between Classes | step budget 13–10,000 | structured no 20/20, 260 steps | unstructured no needed exhaustive search for 20/20; whether NP equals co-NP | | The P vs NP Question | step budget 13–10,000, input size 8–24 | meet-in-the-middle 1357 steps, 20/20 agree | whether the gap closes; the answer to the question | | Approximation and Heuristic Methods | k = 0, 4, 8, 12 | 5/20 exact at k=0, 20/20 exact at k=8 | that k=8 will be exact on every input; a proven approximation ratio | The right column is this course's actual product. Every number in the left column comes from a run; every row in the right column names the place the run **could not reach**. This is the course that shows where measurement ends. The Computer Science curriculum followed a single axis across eight courses: from the bit's representation in hardware (K01) to writing a program (K02), the layout of data (K03), measuring a method's cost (K04), sharing the machine (K05), showing the system (K06), comparing hard problems against an oracle (K07), and the limit of measurement (K08) — at every layer, cost was **counted**, and a cost not counted did not count as known. **Two debts owed by K07 are paid off in this course.** The first was the question "why is this problem hard," which the traveling salesman and Hamiltonian path lessons each referred forward to here in a separate section. The answer is not a proof but a **classification**: these problems' "yes" answer is cheaply verified with a short certificate (`02`), their difficulty is carried between them by cheap reductions (`03`), and the "no" answer does not accept the same discount (`04`). The names of these classes are NP, NP-complete, and NP-hard. The second was the question from K07's course closing: is not knowing anything better than **brute force** a fact about our knowledge, or a fact about the problems. This question has a name, and it is the **P vs NP question** (`05`). Its answer is not known. The debt is paid not by answering the question, but by **naming it correctly** and showing why it is not answered: measurement can count a method's steps; it cannot speak about every method. The next curriculum is **Linux and System Administration**, and it changes the ground under the discussion. Computer Science established and modeled concepts; Linux and System Administration takes up the same concepts' counterpart in a **running system**: the shell, the file system, processes, services, the network, and kernel interfaces. Computer Science's Processes and Threads topic modeled and counted processes and the file system; Linux and System Administration uses the same concepts at the **command** level. The first question fits this transition: what is the interface for talking to a system, and how far down does a command given at that interface descend.