skip to content

A teammate says a task is in NP and therefore needs exponential time. What does NP membership actually claim?

level: juniorimportance: must knowfreq 74%

answer

  1. a class about checking, not solving
  2. someone hands you a candidate answer
  3. the checker runs in polynomial time
  4. the hint has to stay short
  5. easy problems live in NP too

basics

~20 s

NP membership claims only that a yes-answer has a short certificate a checker can validate in polynomial time. It says nothing about how long finding that answer takes, and it does not exclude an easy problem.

solid answer

~50 s

NP is defined by checking, not by solving. A decision problem is in NP when there is a verifier: a deterministic procedure that takes the instance plus a second string, the certificate, runs in time polynomial in the instance size, accepts at least one certificate for every yes-instance, and accepts none at all for a no-instance. Nothing in that definition forbids a fast algorithm, so every problem in `P` is also in NP — the verifier simply ignores the certificate and decides directly. The `N` is for nondeterministic: a machine allowed to branch and to accept if any branch accepts, where the branch choices are exactly the certificate. The teammate is conflating NP with the hardest problems inside it, and even for those the exponential claim is a widely held belief rather than a theorem, because P versus NP is open.

go deeper

for a junior

Recall the one-line definition: a yes-answer comes with a short hint that a fast checker can validate. Say plainly that this is about checking, not about how long solving takes.

for a middle

Explain the verifier formally: two inputs, polynomial time in the instance size, a certificate for every yes-instance and none for a no-instance. Show why P sits inside NP.

for a senior

Demonstrate that you can correct the claim without overcorrecting: no theorem says these problems need exponential time, and enumerating certificates already gives an exponential upper bound.

for a principal

Frame it for a team: 'in NP' is an auditability property you can design around, since it means a produced answer can be rechecked cheaply, independently of how the answer was found.

## What membership in NP actually says NP is a class of **decision problems** — questions whose answer is yes or no on a given instance, such as 'does this graph contain a tour visiting every city once with total cost at most B?'. A decision problem belongs to NP when a **verifier** exists for it. The verifier is an ordinary deterministic procedure with two inputs: the instance `x`, and a second string `w` called the **certificate** or **witness**. Three conditions pin the definition down: - **Shortness.** Some fixed polynomial `p` satisfies `|w| <= p(|x|)` for the certificates that matter. The proof must be short relative to the question. - **Checkability.** The verifier runs in time polynomial in `|x|`. Given the pair, it answers accept or reject and never searches. - **Soundness and completeness.** Every yes-instance has at least one certificate the verifier accepts; every no-instance has *none at all*. A verifier that can be fooled by some string on a no-instance is certifying a different problem. That is the whole definition, and it prices exactly one thing: **checking a single candidate answer**. It is silent on where the candidate came from. ## Why 'in NP, therefore exponential' is false | Claim | Status | |---|---| | Every problem in NP has a short checkable certificate for its yes-instances | True — that is the definition | | A problem with a polynomial-time algorithm cannot be in NP | False — `P` is contained in NP | | Every problem in NP needs exponential time | False as stated; no such theorem exists | | Some problems in NP have no known polynomial algorithm | True, and whether that is permanent is the open P versus NP question | | A problem in NP might be undecidable | False — enumerating all certificates decides it, in exponential time | The last row matters more than it looks. Because certificates are at most `p(|x|)` bits long, there are at most `2^p(|x|)` of them; trying each one with a polynomial check terminates. So membership in NP is an **upper bound on difficulty**, not a lower bound: it says the problem is decidable and that its yes-answers are auditable. It never says the problem is hard. The teammate has heard the phrase attached to famously stubborn problems and generalised the wrong direction. ## Where the N comes from The historical definition is a **nondeterministic** polynomial-time machine: one allowed to branch at each step, accepting the input if at least one branch accepts. The two formulations are the same class: 1. From a branching machine to a verifier: take the sequence of branch choices along one accepting run as the certificate. The run is polynomially long, so the choices are polynomially many bits, and replaying them deterministically is a polynomial-time check. 2. From a verifier to a branching machine: branch to guess the certificate bit by bit, then run the verifier on it. This is why 'guess and check' is a fair informal reading of NP. The guessing half is free in the model and expensive in reality; the checking half is the part the definition actually constrains. ## What the definition does not promise - **Nothing about searching.** A polynomial verifier gives you no procedure for producing a certificate, only for auditing one. - **Nothing about no-instances.** The certificate exists on the yes side only. Short proofs of absence are the subject of a different class, and the two are not known to coincide. - **Nothing about the optimisation version.** 'Is there a tour of cost at most B?' is the decision version, and it is the one NP is about. 'What is the cheapest tour?' is a search or optimisation question, and its answer is not a yes or a no, so it does not sit in NP as stated. - **Nothing about a specific algorithm.** Membership is a property of the problem, not of the code someone wrote for it. ## Answering it at the whiteboard A compact reply: 'NP is the class of decision problems whose yes-answers have a short certificate that a polynomial-time checker can validate. Easy problems are in NP too — the checker can just solve them. The problems you are thinking of are the hardest ones inside NP, and even for those, exponential time is what we currently know how to do, not something anyone has proved is necessary.'

  • Is every problem solvable in polynomial time also in NP?
    Yes. Build a verifier that ignores the certificate entirely and runs the polynomial-time algorithm on the instance. It accepts exactly the yes-instances, accepts nothing on a no-instance, and runs in polynomial time, so the definition is satisfied. That containment is why 'in NP' never implies 'hard'.
  • What does the N in NP abbreviate, and what machine does it describe?
    Nondeterministic. The original definition is a machine that may branch at each step and accepts if at least one branch accepts, within polynomial time. The branch choices along an accepting run are exactly a certificate, which is why the guessing machine and the verifier define the same class.
  • Does membership in NP tell you anything about the no-instances?
    No. The definition promises a certificate only for yes-instances, and requires that no-instances have none. Short proofs that the answer is no are a separate question, handled by the complement side of the class, and the two sides are not known to match.

saying these in an interview costs you the question

  • Says NP stands for non-polynomial
  • Claims every problem in NP requires exponential time
  • Believes a problem with a fast algorithm cannot be in NP
  • Treats NP and NP-hard as the same label
  • Says a problem in NP might be undecidable
  • Thinks the checker is supposed to find the certificate itself