P — polynomial time: Question bank — Coding deep dive

The one rule that catches most mistakes: time is measured against the length of the input (its bits), never the value it represents. Keep that in your pocket — the figure below shows exactly why it fools people.

Read the picture: the number $N$ sits on the left as a value; on the right it is written out in only $n = lo g_{2} N$ bits (its length). An algorithm that does $N$ work looks small next to $N$ , but stacked against the short bit-string $n$ it is $2^{n /2}$ — the red exploding curve. That gap is the PRIMES trap.

First: what is a "language", and how do inputs become strings?

Before we can talk about P as "a class of languages", we have to say plainly what those words mean — the parent note used them freely, so this page earns them.

The two cost models you need

The traps below assume two "cost models". They should be stated outright, with the machine they run on named, so here they are before you meet them.

True or false — justify

Trial division proves that PRIMES is in P.

False — trial division runs in about

N

steps, but the input length is

n = lo g_{2} N

bits, so

N = 2^{n /2}

is exponential in

n

; PRIMES ∈ P needs the AKS algorithm which is poly in

n

n^{100}

-time algorithms are excluded from P because they are too slow.

False —

n^{100}

is a polynomial, so it is squarely in P; P is a theoretical feasibility line, not a promise of speed.

If a problem is in P then every algorithm for it runs in polynomial time.

False — membership only requires one poly-time algorithm to exist; the same problem can also have slow exponential algorithms.

P is defined only for yes/no (decision) problems.

True — P is a class of languages (sets of strings, i.e. membership questions); optimization problems enter via their decision versions ("is there a solution of cost

\leq B

?").

Whether a problem is in P depends on whether you use a Turing machine or a real laptop.

False — by the Cobham–Edmonds thesis, reasonable deterministic models simulate each other with polynomial overhead, so membership in P is the same on all of them.

P is closed under complement.

True — run the poly-time decider, then flip yes↔no; that is one extra step, so the total is still polynomial.

2^{n}

is basically polynomial because for

n = 10

it is only

1024

False — class membership is about asymptotic growth for all large

n

; one small comfortable value says nothing about the explosion later.

A polynomial composed inside another polynomial can grow exponentially.

False —

c^{'} (c n^{k})^{j} = c^{'} c^{j} n^{k j}

stays polynomial; this closure under composition is exactly why P is a stable class.

A \in P

and

B \in P

then

A \cap B \in P

True — decide

x \in A

and

x \in B

each in poly time and answer "yes" only if both say yes; poly + poly = poly.

A problem with no known polynomial algorithm is definitely not in P.

False — "not yet found" is not "does not exist"; PRIMES was widely believed in P long before AKS actually proved it.

Spot the error

"Multiplying an

n

-digit number by

n

: since we add the number to itself

n

times, that's

n

additions, so it's linear — trivially in P."

The error is calling it "

n

additions"; each addition of

n

-bit numbers already costs

O (n)

bit operations (see the bit-cost model), so repeated addition is

O (n^{2})

— still poly, but the "linear" claim is wrong.

"Reachability needs to try all paths, and a graph can have exponentially many paths, so

s

–

t

path is not in P."

BFS/DFS never enumerates paths — it visits each vertex and edge a bounded number of times for

O (V + E)

; you don't count paths, you count the

V

dots and

E

lines.

"An algorithm that takes

N

steps on numeric input

N

is polynomial, since

N

is smaller than

N

Smaller than

N

is irrelevant; the input length is

n = lo g_{2} N

bits and

N = 2^{n /2}

, which is exponential in that length.

"P is closed under composition, so combining any two things in P keeps you in P — even calling a P-subroutine exponentially many times."

The closure only holds when the subroutine is called a polynomial number of times; a polynomial subroutine invoked

2^{n}

times is exponential overall.

L \in P

means we can decide it, so P is just the class of decidable languages."

Decidability alone is far weaker — plenty of decidable languages need exponential (or worse) time; P demands a polynomial time bound on top of always halting correctly.

"Karatsuba multiplication is

O (n^{1.585})

, and

1.585

isn't an integer, so it isn't polynomial."

Polynomial time just means

O (n^{k})

for some constant

k > 0

;

k

need not be an integer, so

n^{1.585}

is perfectly polynomial.

Why questions

Why does P insist on a deterministic Turing machine rather than a nondeterministic one?

Because determinism follows a single computation path (see the branching figure); allowing guessing spreads into many parallel paths and gives the strictly different (and possibly larger) class NP — nondeterministic polynomial time.

Why is "polynomial" chosen as the boundary instead of a specific bound like

O (n^{5})

Because polynomials are closed under addition, multiplication, and composition — the algebra

c^{'} (c n^{k})^{j} = c^{'} c^{j} n^{k j}

shows nesting stays polynomial — so combining efficient pieces stays efficient; a fixed exponent like

5

would break the moment you nest two algorithms.

Why do we insist the Turing machine always halts with a correct answer?

A decider must give a definite yes/no on every input; a machine that loops forever on some inputs doesn't decide the language at all, so it cannot witness membership in P.

Why does measuring time in bits (not numeric value) matter so much for number-theoretic problems?

Because a number

N

is written in only

lo g_{2} N

bits, algorithms scaling with

N

N

are secretly exponential in the true input size — this is the classic PRIMES trap in figure s01.

Why is P called "model-robust" and why does that make it a meaningful class?

Because RAM machines, multi-tape TMs, and laptops all simulate each other with polynomial overhead, so the yes/no answer to "is it in P?" doesn't depend on your machine — the class captures something intrinsic, not incidental.

Why can P afford to ignore the constant

c

and the exponent

k

c n^{k}

Because P asks a coarse structural question ("is growth polynomial at all?"); the fine distinctions between

n^{2}

and

n^{3}

belong to Time complexity & Big-O and finer TIME complexity classes.

The determinism-vs-guessing picture behind the first question:

The red single line is the deterministic machine's one path — that is P. The black tree fanning out is nondeterministic branching, where the machine may "guess" — that is NP — nondeterministic polynomial time. Same time budget, wildly different power.

Edge cases

Is a problem solvable in constant time (independent of

n

) in P?

Yes — constant time is

O (n^{0})

, a degenerate polynomial, so it sits comfortably inside P.

Is the empty language

\emptyset

(always answer "no") in P?

Yes — a machine that halts immediately and rejects runs in

O (1)

, which is polynomial; trivial languages are the easiest members of P.

Is every finite language in P?

Yes, but the reason is subtle — a finite

L

has a longest string of some length

ℓ

; a decider hard-wires this fixed threshold and simply checks

∣ x ∣ \leq ℓ

and then compares

x

against the finitely many members, all in time bounded by a constant depending only on

L

(not on the input), so it is

O (1)

per input.

Does a finite language being in P mean we store an exponentially large lookup table at runtime?

No — the table's size is a constant fixed by

L

, baked into the machine's finite control, not built from the input; it never grows with

n

, so it costs no per-input time or space.

If an algorithm runs in

O (n^{2})

but only when the input is nonempty, and it loops forever on empty input, is the problem in P via this algorithm?

No — a decider must halt on every input including the empty string; failing on the degenerate case disqualifies the algorithm as a P-witness.

Is a problem with a poly-time algorithm whose exponent grows with the input (like

n^{l o g n}

) in P?

No —

n^{l o g n}

is quasi-polynomial, not polynomial, because no fixed constant

k

bounds the exponent; P requires a single

k

that works for all

n

{0, 1}^{*}

(the language of all strings, always "yes") in P?

Yes — accept unconditionally in

O (1)

time; the universal language is a trivial member just like the empty one.

Connections

The map below places this page (red node) among its neighbours; read each arrow as "leads to / is used by", starting from the models that build P and fanning out to the classes P sits inside or is compared against.

What builds P (arrows into the red node): the Turing Machine supplies the deterministic model, Time complexity & Big-O supplies the $c n^{k}$ language for bounds, and the Cobham–Edmonds thesis justifies "polynomial = feasible / model-robust".
Where P lives: P is exactly the union $⋃_{k} TIME (n^{k})$ inside TIME complexity classes.
What P is compared with: NP — nondeterministic polynomial time (P plus a guess step) and the open P vs NP problem asking if they are equal.
The transport machinery: Polynomial-time reductions (relying on the poly∘poly closure above) map problems within P and define the hardest NP-complete problems.