Foundations — NP — non-deterministic polynomial, verifier definition

The parent note throws a lot of symbols at you in one breath: $L$, $x$, $|x|$, $c$, $p$, $V$, $\exists$, $⟺$, and phrases like "polynomial time" and "decision problem." If any of those are fuzzy, the whole definition collapses into noise. So here we earn each one, in an order where every new symbol only uses ones we already built.

0. The picture behind the whole thing

Before any symbol, hold this image: a problem is a giant field of possible answers. Searching the field is slow. But a good tip points you to one spot, and checking that spot is fast.

Everything below is just this picture, translated into precise notation.

1. Decision problem — a yes/no question

Why the topic needs it. NP is defined only for yes/no problems, because the definition talks about which inputs are "yes" instances. If a problem returned a number or a list, the machinery ($x\in L$, one-sided certificates) wouldn't fit.

2. Input $x$ and its size $|x|$

Why the topic needs it. Every speed claim ("polynomial time") is measured relative to $|x|$. Without a clear notion of input size, "fast" and "short" have no yardstick.

3. Language $L$ — the set of all YES inputs

The notation $x\in L$ (read "$x$ is in $L$") means "the input $x$ is a YES instance." $x\notin L$ means "$x$ is a NO instance."

Why the topic needs it. The entire definition of NP is a statement about when $x\in L$. Turning "the answer is yes" into "$x$ belongs to a set $L$" lets us reason with set membership instead of vague English.

4. Polynomial time — the meaning of "fast"

Why the topic needs it. Both the verifier's speed and the certificate's length are bounded "in polynomial time / polynomial size." This is the yardstick behind the whole class.

5. The polynomial $p$ and the bound $|c|\le p(|x|)$

The inequality $|c|\le p(|x|)$ reads: "the length of the certificate is at most $p$ of the input length." In words: the tip must be short relative to the input.

Why the topic needs it. Without this cap you could smuggle in an enormous tip that already contains the full answer — the verifier couldn't even read it in poly time. Step 2 of the parent's derivation is precisely this loophole-fix.

6. Certificate $c$ — the tip / witness / proof

Why the topic needs it. $c$ is the heart of the "easy to check" idea. No certificate → nothing to check → you're back to solving from scratch.

7. Verifier $V$ and the output $V(x,c)=1$

Why the topic needs it. $V$ is the formal machine that captures "checking is easy." Its two arguments and its $1/0$ output are exactly the notation the definition uses.

8. The logic symbols: $\exists$, $\wedge$, $⟺$

Now the parent's defining line reads in plain English:

$x\in L⟺\exists c(|c|\le p(|x|)\wedge V(x,c)=1)$

"$x$ is a YES instance exactly when there exists a tip $c$ that is short enough AND makes the judge ring the bell."

9. Nondeterminism — "magical guessing"

Why the topic needs it. The letter N in NP comes from this model. Understanding that "guess" = "certificate" dissolves the mystery of the name.

Prerequisite map

Everything on the left ultimately feeds the single boxed idea: NP. Notice how "polynomial time" ($D$) feeds three different children — it is the yardstick for both the tip's length and the judge's speed.

Equipment checklist

Self-test: can you answer each before revealing?

Once every box above rings clear, re-read the parent definition — see the topic note — and it should read like plain English. From here the natural next steps are P vs NP Problem, Polynomial-Time Reductions, and NP-Completeness.