Nondeterminism and Certificates

A conflict has a short witness: two rules plus one request that matches both, re-checkable in polynomial time. Absence has no such witness — it is a claim about every possible request, and that asymmetry between existential and universal claims is what co-NP captures.

NP is defined by cheap checking, not by expensive solving. Every polynomial-time problem is already inside NP, and for no NP-complete problem has anyone ever proven a superpolynomial lower bound; exponential is the best known cost, not a floor.

Majority voting over k independent runs drives a two-sided error of 1/3 down exponentially in k: the wrong verdict needs more than half the runs to fail at once, which a Chernoff bound makes vanishingly unlikely. Cost grows linearly, failure falls exponentially.

A composite verdict is a proof and can be trusted outright; a prime verdict is only probable. One-sided error means the certainty lives on exactly one side, which is why repeating with fresh random bases drives the remaining doubt down multiplicatively.

Hand over a nontrivial divisor d with 1 < d < n. The checker performs one division, confirms d divides n exactly, and accepts. That is polynomial in the digit count of n, and the checker never searches.

Co-NP: unsatisfiability is the canonical co-NP-complete problem, the exact complement of satisfiability. Its twin is tautology, since a formula is a tautology precisely when its negation is unsatisfiable, so hardness carries between the two by negation.

It would destroy the assumption. Inverting a function that is cheap to compute forward is a search whose check is one forward evaluation, so if that whole class of searches is polynomial, one-way functions do not exist and every scheme resting on computational hardness falls with them.

Finding would become as cheap as checking. Any object of modest size whose correctness a fast check can confirm — a schedule, a layout, a formal proof of bounded length, a key — could also be produced quickly, so the expensive half of the work disappears.

A checker is handed one candidate; a solver must locate one among exponentially many. Fast checking bounds the cost per candidate, not the number of candidates that must be tried. Whether that gap can always be closed is the open P versus NP question.

It places the problem in NP and co-NP at once. That two-sided certifiability is strong evidence the problem is not among the hardest in NP, because a complete problem sitting in co-NP would force the two classes to coincide — and such problems often turn out to be polynomial-time solvable.

Finding needs one witness; counting needs all of them without double counting. Disjunctive terms overlap, so the totals cannot simply be added, and resolving the overlaps is as hard as any counting problem in #P. Easy search says nothing about easy counting.

Without the cap the class stops meaning anything: every semi-decidable problem qualifies, because the transcript of a halting computation is itself a finite certificate. The polynomial bound is what keeps the checker's work polynomial in the instance.

Decide by the shape of the claim, not the budget. A proof of absence is a universal claim, complete for co-NP while conditions stay expressive. Either restrict the condition language until the claim lands in a class closed under complement, or ship a third verdict: unknown.

Hedge against one assumption falling, not against the whole edifice collapsing. Buy replaceability, assumption diversity and an explicit secrecy lifetime for the data; do not buy insurance against a universal collapse, which would have no product-level answer anyway.

It is defensible when the exact answer is genuinely out of reach or disproportionately costly, the failure probability is written down and driven below the system's other failure rates, and the randomness is real. It is not defensible as a claim of asymptotic speed.

Equality would mean every tautology has a short, checkable proof — a uniformly short refutation for every unsatisfiable formula. Decades of work on proof length have produced no such system, and superpolynomial lower bounds are theorems for the weaker systems analysed so far.

Three things stay out of reach: problems with no algorithm at all, problems above NP such as the complete problems for polynomial space, and anything whose new polynomial algorithm carries a degree or a constant so large that the bound is theoretical only.

The signs make the determinant change predictably under row operations, so elimination evaluates it in cubic time without touching its factorially many terms. The permanent has no cancellation to exploit, and computing it is #P-complete: it counts a bipartite graph's perfect matchings.

Query it repeatedly on modified instances: pin one package to one version, ask again, keep the pin when the answer stays yes and try the next version otherwise. Polynomially many queries build the whole set.