Why does NP bound a certificate's length by a polynomial instead of only requiring that some finite certificate exist?

## Two ways to write the same definition Both phrasings appear in the literature and they describe the same class: | Phrasing | Certificate length | Verifier time budget | |---|---|---| | A | Unrestricted in the text | Polynomial in `|x|` alone | | B | `|w| <= p(|x|)` for a fixed polynomial `p` | Polynomial in `|x| + |w|` | Phrasing A restricts the length implicitly: a machine that runs for `q(|x|)` steps cannot read more than `q(|x|)` symbols of anything, so a longer certificate contributes nothing the verifier can see. Phrasing B restricts it explicitly and then permits the verifier to be measured against the combined size, which is harmless once the certificate is already polynomially capped. What you may **not** do is take phrasing B's time budget while dropping phrasing B's length cap. That combination is the trap this question is about. ## What dropping the cap actually admits Suppose the only requirement is that some finite certificate exists and that the checker runs in time polynomial in the certificate's own length. Then take any problem for which a procedure eventually halts and says yes on the yes-instances: 1. Let the certificate be the **complete transcript** of that halting computation: the sequence of configurations from the start to the accepting state. 2. The checker verifies the transcript locally — the first configuration matches the input, each configuration follows from its predecessor by one legal step, the last one accepts. 3. Each of those checks inspects a bounded neighbourhood, so the whole check is polynomial in the transcript's length. Every such problem now has a 'certificate'. The resulting class is the **semi-decidable** problems, and it contains problems with no algorithm that halts on the no-instances at all. Nothing about time or feasibility has been said; the word 'polynomial' in the definition has been made to do no work whatsoever. Allowing certificates that are merely exponentially long is less extreme but still fatal to the meaning: the class you get sits far above NP, and its problems need exponential time even to **read** the proof, let alone to find it. The polynomial cap is the line at which 'proof' still means something a machine bounded by the question's size can consume. ## The practical reading This is not only a definitional nicety. Picture a dependency resolver that must return, alongside its chosen version set, a proof artefact a reviewer can recheck by hand: - A **short** artefact — the chosen versions, plus which constraint each satisfies — is polynomial in the instance and a reviewer can walk it. - The **complete search log** is also a proof in the everyday sense: it really does establish the answer. But its size is not bounded by any polynomial in the instance, so 'rechecking' it means redoing the search. That artefact is not a certificate; it is the work. The distinction between a proof you can check and a proof you can only re-derive is precisely the distinction the polynomial bound draws. ## Two details worth having ready - **Which polynomial does not matter.** The definition fixes a polynomial per problem, and the class is the union over all of them. A certificate of size `n^5` is as legal as one of size `2n`; what is forbidden is a length that outgrows every polynomial. - **The bound is on the certificate, not on the number of certificates.** There are still up to `2^p(|x|)` strings of the permitted length. Bounding length keeps checking cheap; it does nothing to make searching cheap, and conflating the two is a separate error. ## How to spot the mistake in your own phrasing Whenever you describe NP, check which quantity the word 'polynomial' is attached to. 'The checker runs in polynomial time' is incomplete until you say **polynomial in what**. Measured against the instance, the definition is the intended one. Measured against the certificate alone, with the certificate unbounded, you have quietly defined the semi-decidable problems and lost every guarantee the class was invented to express.