--- title: 'co-NP and Relationships Between Classes' source: 'https://academia.sh/en/courses/theory-of-computation/co-np-and-relationships-between-classes' course: 'Theory of Computation' language: en updated: '2026-08-17T18:08:29+00:00' license: 'CC BY-SA 4.0' --- # 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 less 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.