Complexity Classes

Polynomial time is a claim about scaling, not about one machine. A polynomial bound survives a change of machine model and stays polynomial when routines call each other; a fixed step budget expires with the next hardware or the next larger input.

None of those four adjacent steps is proven strict; each one is open. The proven separations skip levels: the time hierarchy theorem puts P strictly inside EXPTIME, which forces at least one step in between to be strict.

Logarithmic space counts only the read-write work tape. The input is already present, read-only and freely re-readable, so charging for it would put every problem at n cells and leave no sublinear class at all.

Input length is the number of symbols needed to write the instance down, not the value it denotes. An amount of value V occupies about log2(V) bits, so a loop running V times runs exponentially many steps in that length.

Because the encoding fixes what the input length is. Written in tally marks, a value of one million is a million symbols long, so a per-unit scan is linear; written in any base of two or more it is twenty bits, and the same scan is exponential.

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.

A conflict has a short witness: two rules plus one request that matches both, re-checkable in polynomial time. Absence has no such witness — it is a claim about every possible request, and that asymmetry between existential and universal claims is what co-NP captures.

NP is defined by cheap checking, not by expensive solving. Every polynomial-time problem is already inside NP, and for no NP-complete problem has anyone ever proven a superpolynomial lower bound; exponential is the best known cost, not a floor.

Majority voting over k independent runs drives a two-sided error of 1/3 down exponentially in k: the wrong verdict needs more than half the runs to fail at once, which a Chernoff bound makes vanishingly unlikely. Cost grows linearly, failure falls exponentially.

A composite verdict is a proof and can be trusted outright; a prime verdict is only probable. One-sided error means the certainty lives on exactly one side, which is why repeating with fresh random bases drives the remaining doubt down multiplicatively.

Two colours leave no freedom: fix one vertex and propagation forces every other, so one traversal either succeeds or exposes an odd cycle. A third colour restores a choice at each vertex, and those choices interact globally.

A hardness proof normally transfers hardness from a problem already known complete, and at the time none existed. Cook-Levin therefore argued about every problem in NP at once, encoding an arbitrary verifier's computation directly as a Boolean formula.

NP-hard only says everything in NP reduces into the problem; it does not place the problem in NP. Optimization phrasings, which are not decision problems, and the halting problem, which is undecidable, are NP-hard and outside NP.

An NP-completeness claim owes two proofs: membership, that a short certificate for a yes answer is checkable in polynomial time, and hardness, that an already-complete problem reduces into it. Proving only the second gives NP-hardness, not completeness.

An O(n*T) table is pseudo-polynomial: T is a numeric value carried by only about log T digits, so the table is exponential in the instance's written length, not polynomial in it.

Deciding whether an arbitrary program stops is undecidable, so no checker can be always-terminating, never-wrong and complete at once. Every real loop detector therefore misses cases, raises false alarms, or sometimes fails to answer.

Assume a routine that always terminates and correctly reports whether any program halts on any input. Write a program that asks it about itself and then does the opposite. Running that program on its own text makes the routine wrong either way.

The opposite of the claim. Mapping your task into SAT shows the task is no harder than SAT, an upper bound. Hardness needs the reverse map: a known-hard problem translated into your task.

A polynomial-time many-one reduction turns any instance of A into one instance of B using only polynomial work, and guarantees the answer survives the trip: yes maps to yes, and no maps to no.

Line count is a syntactic property, readable from the text itself. Whether a function ever returns a negative number is a property of the function it computes, and Rice's theorem makes every nontrivial property of that kind undecidable.

Strip the domain nouns and restate the requirement as objects, a relation between them, and an objective. That skeleton — cover everything, pick a subset under a budget, order with no repeats — is what you match against the known catalogue.

A 2-approximation promises that on every input the returned cost is at most twice the best possible cost. It is a proven worst-case ceiling on answer quality, not an average over inputs and not a statement about running time.

The incumbent is the best complete plan found so far, and its cost is the cut-off. The bounding function computes an optimistic cost for everything still reachable in a subtree; if that is no better, the subtree is discarded unexplored.

The exponent's home decides it. In 2^k times n only the small conflict count k sits in an exponent, so a bigger graph costs a linear factor more. In n^k the graph itself is raised to k, so growth is fatal.

Routine, hard, or impossible. Routine needs a named polynomial method that fits; hard needs a known NP-complete problem sitting inside the requirement; impossible needs the shape of a question about what an arbitrary program does at runtime.