skip to content

An interviewer asks you to exhibit the NP certificate for the claim that an integer is composite. What do you hand over?

level: middleimportance: must knowfreq 57%

answer

  1. hand over data, not a procedure
  2. one candidate, never the search
  3. short relative to the digit count
  4. the checker only validates
  5. a no-instance must have none

basics

~20 s

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.

solid answer

~50 s

The certificate is data, not a procedure: a single integer `d` with `1 < d < n`. The verifier divides `n` by `d`, checks the remainder is zero and that `d` is in range, then accepts. Both the certificate and the work are polynomial in the **number of digits** of `n`, which is the input size — `d` has at most as many digits as `n`, and one division is cheap in that measure. Notice what the verifier is spared: finding `d` by trial division would run in time proportional to the square root of the *value*, which is exponential in the digit count. That gap is the whole point of the verifier formulation. Soundness holds because a genuine prime has no such `d` in range, so no string can make the checker accept on a no-instance.

code

pseudocode · 22 lines
pseudocode
check_tour(graph, cities, budget, order):
    n = count(cities)
    if length(order) != n:
        reject

    seen = empty set
    for each c in order:
        if c in seen:
            reject
        add c to seen

    cost = 0
    for i = 0 to n - 1:
        a = order[i]
        b = order[(i + 1) mod n]          // wraps back to the start
        if there is no edge (a, b) in graph:
            reject
        cost = cost + weight(a, b)

    if cost > budget:
        reject
    accept

go deeper

for a junior

Remember that a certificate is a piece of data you could email to someone, such as a divisor or an ordering, and that the checker only confirms it.

for a middle

Explain the check step by step and state its cost in the right measure: the digit count of the number, or the number of cities, never the numeric value.

for a senior

Show the soundness half too: name what makes a no-instance uncertifiable, and resist the slide from certifying a budget to certifying an optimum.

for a principal

Treat the witness as a design artefact: when an internal solver emits one, reviewers and downstream systems can audit results without trusting or rerunning the solver.

## What has to be true of a certificate Exhibiting a witness is the exercise interviewers use to find out whether the definition of NP is understood or merely recited. Three properties must hold, and candidates usually drop the third: - **It is data, and it is short.** The certificate is a string whose length is bounded by a fixed polynomial in the instance size. Not an algorithm, not a promise, not a log of how it was obtained. - **A polynomial-time checker validates it.** The checker reads the instance and the certificate and answers accept or reject. It performs no search of its own. - **It is sound as well as complete.** Every yes-instance has at least one accepted certificate, and no-instances have **none**. If some string can make the checker accept a no-instance, the checker certifies a different problem. ## Compositeness, worked end to end The instance is an integer `n` written in binary or decimal; the question is whether `n` is composite. The certificate is a **nontrivial divisor**: an integer `d` with `1 < d < n` and `n mod d == 0`. Take `n = 91`. The certificate is `d = 7`. The checker divides: `91 = 7 * 13`, remainder zero, and `1 < 7 < 91`, so it accepts. It never learned that the cofactor is 13 and did not need to. The decisive detail is **which encoding measures the input**. The input size is the number of digits, roughly `log n`, not the value `n`. So: | Quantity | Size in the input measure | |---|---| | The certificate `d` | At most as many digits as `n` — polynomial | | One division with remainder | Polynomial in the digit count | | Searching for `d` by trial division | Up to about `sqrt(n)` trials — exponential in the digit count | A candidate who says 'just try all divisors, that is fast' has silently switched to measuring the input by its value. Reading `n` costs `log n` symbols; an algorithm allowed `sqrt(n)` steps is allowed exponentially many steps in that measure. ## A second witness: a tour in visiting order The same shape works for a graph question. Instance: a graph with weighted edges, a set of cities, and a budget `B`. Decision version: is there a tour that visits every city exactly once and returns to the start, with total cost at most `B`? The certificate is **the cities listed in visiting order**. Size: a permutation of `n` cities is `n` labels of about `log n` bits each, so roughly `n log n` bits — comfortably polynomial. The checker does four things: confirms the list has `n` entries with no repeats, confirms every consecutive pair is an edge, confirms the pair closing the cycle is an edge too, and sums the weights to compare against `B`. All linear in the list. Note what this certificate does **not** prove: that the tour is the cheapest one. That would require ruling out every cheaper tour, which is an absence claim, and absence is not what this certificate carries. Certifying an optimum and certifying a budget are different tasks, and only the second is what the decision version asks. ## What people offer that is not a certificate 1. **The algorithm that would find the answer.** A procedure is not a witness; the verifier already has procedures, what it lacks is the answer. 2. **The assertion itself.** 'It is composite' is the claim, not evidence for it. 3. **A transcript of the exhaustive search.** It genuinely convinces, but it is exponentially long, so no polynomial-time checker can read it. 4. **A partial hint that still leaves searching to do.** 'A factor lies between 5 and 500' forces the checker to search, which the definition forbids. ## How to present it Say the certificate, say the check, say the size, say why a no-instance has none. Four sentences. 'For compositeness the witness is a nontrivial divisor; the checker does one division; the witness is no longer than the input; and a prime has no divisor in that range, so nothing can fool the checker.' The same four-part shape works for any problem you are asked to place in NP, and reaching for it immediately is the signal the question is testing.

  • What is the certificate for the claim that a graph has a tour visiting every city once within a cost budget?
    The cities listed in visiting order. The checker confirms the list is a permutation of the cities, that every consecutive pair including the wrap-around back to the start is an edge, and that the summed weights do not exceed the budget. That is about `n log n` bits and a linear pass.
  • Why does soundness matter as much as shortness?
    Because a checker that accepts some string on a no-instance is deciding a larger set of instances than the problem asks about. Completeness alone would let a checker that accepts everything qualify. Both halves together are what make acceptance equivalent to the answer being yes.
  • Does the checker need to know how the certificate was produced?
    No, and that independence is the useful part. The verifier is a function of the instance and the string in front of it, so a solver can be untrusted, slow, randomised or replaced entirely, and the audit still holds. This is what lets a reviewer recheck an answer by hand.

saying these in an interview costs you the question

  • Offers the search algorithm instead of a piece of data
  • Expects the checker to find the divisor itself
  • Calls trial division a polynomial check on the digit count
  • Measures the input size by the value rather than the digits
  • Claims the same divisor certificate also proves that n is prime
  • Says the tour certificate proves the tour is the cheapest one