P vs NP — statement, why it matters: Foundations

This is the prerequisite page for the P vs NP topic. The parent note throws around $n$ , $O (n^{k})$ , "decision problem", "certificate", $P \subseteq N P$ , and more. Here we earn every one of those from zero, in the order they build on each other.

1. A "problem" — but a very specific kind

Before we can say "hard" or "easy", we must pin down what a problem is.

Figure s01 shows this as a machine with one input slot and exactly two lamps — a green YES lamp and a red NO lamp. Every decision problem is the question "which lamp lights up?"; look at how exactly one lamp ever lights.

Figure — P vs NP — statement, why it matters

2. Input size $n$ — the ruler we measure against

We say some problems are "harder for big inputs". But big needs a number.

Figure s01 also hints at this: the input arrives written out on tape squares; $n$ = how many squares are filled. (That tape is literally a Turing machine tape.)

3. Counting steps, and the symbol $O (\cdot)$

Now: "harder" = "takes more steps as $n$ grows". We need a way to describe growth while ignoring petty details. (Recall a step is one basic tape action of our algorithm, defined at the top.)

Figure s02 is the heart of the whole topic: it plots a polynomial curve $n^{2}$ (teal) against an exponential curve $2^{n}$ (orange). Watch how they start close near the left, then the orange curve rockets almost straight up.

4. The class $P$ — problems we can solve fast

Picture a box labelled $P$ . Inside it sit problems like "is $x$ in this sorted list?" (solvable by binary search, $O (lo g n)$ , which is below any $n^{k}$ ). We draw that box explicitly in figure s04.

5. Certificate, verifier, and the class $N P$

Here is the subtle idea the whole topic hinges on: checking an answer vs finding it.

Figure s03 draws the verifier as a bouncer at a door: $x$ (teal arrow) is "the club rules", $c$ (plum arrow) is "your ID". The bouncer glances (fast) and admits or rejects. A good hint gets you in; no fake hint gets a non-member in.

6. The symbols $\subseteq$ , $=$ , and $= ?$

Now the notation that states the actual question.

Figure s04 shows the $P$ blob nestled inside the $N P$ blob. The million-dollar mystery is whether those two blobs are actually the same blob.

7. Two more words the parent leans on

Definition Reduction (informal)

To reduce problem $A$ to problem $B$ means: ==use a fast translator algorithm that rewrites any question of type $A$ into a question of type $B$ , so that the two always have the same YES/NO answer.== Then a solver for $B$ also answers $A$ : translate, solve $B$ , report its answer. Why must the translator itself run in polynomial time? Because the whole point is to transfer efficiency. If solving $B$ is fast but the translation step were slow (say exponential), the combined "translate-then-solve" recipe for $A$ would be slow too — you'd have proven nothing about $A$ 's tractability. Keeping the translator polynomial guarantees: fast $B$ solver $\Rightarrow$ fast $A$ solver. Why must YES/NO be preserved exactly? If the translation could turn a YES-instance of $A$ into a NO-instance of $B$ (or vice-versa), then $B$ 's answer would be the wrong answer for $A$ . Answer-preservation is what lets us trust $B$ 's verdict as $A$ 's verdict. Detail in NP-Completeness and Reductions.

How these foundations feed the topic

Equipment checklist

Cover the right side and answer each before moving to the parent note.

An "algorithm" is

a finite, fixed recipe of unambiguous steps (here, actions of a Turing machine on a tape) turning input into output.

A "step" that we count is

one basic tape action of the algorithm — read a square, write a square, or move left/right.

A "decision problem" is

a question with only YES or NO as the answer.

The symbol

n

(also

∣ x ∣

) stands for

the input size — the number of symbols (bits) in the encoded input.

Why the choice of alphabet (bits vs digits) doesn't matter

different fixed alphabets change lengths only by a constant factor, which Big-O absorbs.

All our time bounds are measured in the

worst case — the most steps over all inputs of size

n

T (n) = O (f (n))

means precisely

there exist constants

c > 0

and

n_{0}

such that

T (n) \leq c \cdot f (n)

for all

n > n_{0}

Polynomial time means

O (n^{k})

for a fixed constant

k

— variable in the base.

Exponential time means

O (c^{n})

for a fixed constant

c > 1

— variable in the exponent.

The class

P

all decision problems a deterministic algorithm can solve in worst-case polynomial time.

Why

O (lo g n)

counts as being in

P

lo g n = O (n^{k})

for any fixed

k > 0

, so it is below polynomial.

A certificate (witness) is

a short hint whose length

∣ c ∣

is polynomial in

∣ x ∣

, used to confirm a YES answer.

A verifier

V (x, c)

does

checks in time polynomial in

∣ x ∣

whether

x

is a YES-instance, using hint

c

The class

N P

problems whose YES-answers can be verified fast given a poly-length certificate.

"NP" stands for

Nondeterministic Polynomial — verifiable fast, NOT "non-polynomial".

A \subseteq B

means

every element of

A

is also in

B

(A sits inside B).

Why

P \subseteq N P

a fast solver acts as a verifier that ignores the hint and just solves it.

P = ? N P

asks

is every check-easy problem also solve-easy? (open — unknown).

A reduction from

A

B

must be poly-time because

otherwise a slow translation would ruin the efficiency transfer — fast B would not give fast A.

A reduction must preserve YES/NO because

else B's answer would be the wrong answer for A; preservation makes B's verdict trustworthy as A's.

NP-complete means

N P

and every

N P

problem reduces to it — the hardest problems in

N P

Connections

Parent: P vs NP statement & stakes
Decision Problems and Languages
Big-O and Time Complexity
Turing Machines (Deterministic vs Nondeterministic)
NP-Completeness and Reductions
SAT and Boolean Satisfiability
Cook–Levin Theorem