co-NP and Relationships Between Classes

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.”

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.

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.

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.