Mathematical and Algorithmic Prerequisites

The proof, asymptotic, graph, probability, and machine-model tools used throughout complexity theory.

Goals

• Read asymptotic claims with their quantifiers and hidden constants exposed.
• Measure an instance by the length of its encoding, not by the value it represents.
• select and write direct, inductive, contradictory, diagonal, and counting proofs.
• Use finite probability spaces, conditional probability, expectation, and union bounds safely.

1. What complexity measures

Complexity theory asks how many resources are sufficient or necessary as the input grows. The variable is normally the encoding length $n=|x|$. If the mathematical input is the integer $N$, its binary representation has length $\lfloor\log_2 N\rfloor+1$, whereas its unary representation has length $N$. Thus an algorithm taking $O(N)$ steps is exponential in the binary input length but linear in the unary length. Encoding is not clerical detail: it determines the question.

A decision problem is represented by a language $L\subseteq\Sigma^*$. A decider $M$ must halt on every input and satisfy

An algorithm is the abstract method; a machine model specifies which operations count as one step. Later lessons use Turing machines so that “time” and “space” have precise meanings. Robust complexity classes tolerate reasonable simulation overhead, but an analysis must still name its model and encoding.

2. Sets, strings, functions, and graphs

For an alphabet $\Sigma$, $\Sigma^*$ contains all finite strings, including the empty string $\varepsilon$. Concatenation is written $xy$, and $|x|$ is length. A tuple needs a uniquely decodable encoding such as $\langle x,y\rangle$; merely writing $xy$ can be ambiguous. A function $f:\mathbb N\to\mathbb N$ is increasing if $a\le b$ implies $f(a)\le f(b)$, and it is unbounded if every constant is eventually exceeded.

A graph $G=(V,E)$ may be encoded by an adjacency matrix using $\Theta(|V|^2)$ bits or by an edge list using $O((|V|+|E|)\log |V|)$ bits under a standard vertex-numbering convention. A polynomial-time claim under one reasonable graph encoding usually transfers to another only after proving a polynomial relation between encoding lengths.

Worked encoding example. Suppose an algorithm enumerates all integers from $0$ through $N$. It takes $\Theta(N)$ iterations. On input $1^N$ this is linear. On the binary encoding of $N$, whose length is $n=\Theta(\log N)$, it takes $2^{\Theta(n)}$ iterations. The code did not change; the complexity statement did.

3. Asymptotic notation with quantifiers

For eventually nonnegative functions,

Big-$O$ is an eventual upper bound, not equality. Small-$o$ is strict asymptotic domination. For example, $n^2=o(n^3)$, but $3n^2\not=o(n^2)$.

Claim. $4n^2+3n+9=\Theta(n^2)$.

Upper bound. For $n\ge1$, $3n\le3n^2$ and $9\le9n^2$, so $4n^2+3n+9\le16n^2$. Choose $c=16,n_0=1$.

Lower bound. For every $n$, $4n^2+3n+9\ge4n^2$. Choose $c'=4,n_0'=1$. Both quantified witnesses are required.

Useful growth facts include

Changing a logarithm's constant base changes it by a constant factor. Moving a constant into an exponent is different: $2^{cn}$ and $2^n$ are generally not within a constant multiplicative factor.

Use the visualization by choosing an input size and comparing the same functions on linear and logarithmic vertical scales. The order is asymptotic; crossings at small $n$ do not invalidate it.

4. Proof methods

Direct proof and construction

To prove $A\subseteq B$, begin with an arbitrary $x\in A$ and derive $x\in B$. To prove membership in a complexity class, construct one machine meeting both correctness and resource bounds. A slow alternative algorithm does not disprove membership because class membership is existential.

Contrapositive and contradiction

The contrapositive of $P\Rightarrow Q$ is $\neg Q\Rightarrow\neg P$ and is logically equivalent. A contradiction proof assumes the negation of the desired statement and derives an impossibility. Always state what was negated: negating $\forall x\,\exists y\,R(x,y)$ yields $\exists x\,\forall y\,\neg R(x,y)$.

Induction

For a statement $P(n)$, prove a base case and then $P(n)\Rightarrow P(n+1)$. Strong induction may assume all earlier cases. In machine simulations, the invariant often says: “after $i$ simulated steps, the encoding represents exactly the simulated machine's configuration after $i$ steps.” The base case verifies the initial encoding; the step verifies one transition.

Counting and pigeonhole

If $m$ objects are placed in fewer than $m$ boxes, one box gets at least two objects. Complexity proofs count strings, machines, circuits, or configurations. For example, there are $2^n$ binary strings of length $n$ but $2^{2^n}$ Boolean functions on $n$ bits. This enormous gap underlies many existence arguments, though counting alone may not identify an explicit hard function.

Diagonalization

Given an enumeration $M_1,M_2,\ldots$, define an object that differs from $M_i$ on the $i$th designated input. The hard part is not the slogan “do the opposite”; it is ensuring that the diagonal simulator fits its resource budget and halts. Hierarchy theorems therefore require constructibility and a sufficient asymptotic gap.

5. Probability toolkit

A finite probability space consists of outcomes $\Omega$ and a distribution with total mass $1$. An event is a subset of $\Omega$. Conditional probability is

Events $A,B$ are independent when $\Pr[A\cap B]=\Pr[A]\Pr[B]$. Pairwise independence does not imply mutual independence.

The union bound requires no independence:

If $k$ independent trials each fail with probability $2/3$, the probability all fail is $(2/3)^k$. Independence is essential for multiplication.

For a random variable $X$, linearity of expectation says

even when the $X_i$ are dependent. With indicator $I_i$ for event $A_i$, $\mathbb E[I_i]=\Pr[A_i]$. Thus if $X$ counts successful trials, its expectation is the sum of their success probabilities.

Example: amplification. Suppose an independent run succeeds with probability at least $2/3$. Run it $k$ times and accept if any run succeeds when false acceptance is impossible. Failure requires every run to fail, so it is at most $(1/3)^k$. For two-sided error with majority vote, a concentration bound is needed; simply writing $(1/3)^k$ would be wrong.

“With high probability” normally means probability at least $1-1/n^c$ for some fixed $c>0$, or another explicitly stated bound approaching $1$. It does not merely mean probability greater than $1/2$.

6. Reading and writing formal claims

Quantifier order records dependence. In

the constant may depend on $M$ but not on $x$. Replacing it by $\exists c\,\forall M\,\forall x$ asserts one universal constant and is much stronger. Before manipulating a proof, annotate every constant with what it may depend on.

For a language-class claim, separate three obligations:

1. Semantics: the machine accepts exactly the intended strings.
2. Termination: every required computation halts.
3. Resources: the bound holds for every input of the given length, including no-instances.

Worst-case time is a maximum over inputs of length $n$, not an average and not the time on a convenient example.

Common mistakes

• Hiding a constant that actually depends on the input.
• Measuring a number by its value instead of its bit length.
• Reversing an implication when only its contrapositive is valid.
• Multiplying probabilities without independence.
• Proving correctness only for yes-instances or resource use only on accepting runs.
• Treating $O(f)$ as a function rather than a set of eventual bounds.
• Assuming “polynomial” means practical for every exponent and constant.

Exercises

Exercise 1 — Prove $\Theta$

Prove from the definition that $2n^3+100n^2=\Theta(n^3)$. Exhibit explicit constants and $n_0$ in each direction.

Exercise 2 — Refute $O$

Prove that the claim $2^n=O(n^{100})$ is false. Write the negation of the $O$ definition and complete it.

Exercise 3 — Unary versus binary encoding

Let $A$ be the language of unary inputs $1^N$, and let $B$ be the language of binary encodings of the same integers. An algorithm counts from $0$ to $N$ in $\Theta(N)$ steps. Prove that it runs in linear time in the input length on inputs from $A$, but exponential time in the input length on inputs from $B$. Explain why there is no contradiction.

Exercise 4 — Union bound without independence

We sample $k$ values; for each $i$, the probability that value $i$ is bad is at most $1/n^2$. Prove that the probability that at least one value is bad is at most $k/n^2$, without assuming independence. Deduce the case $k=n$. Explain why one may not multiply success probabilities without an extra hypothesis.

Exercise 5 — Expectation with dependence

Let $G=(V,E)$ be a graph. For each vertex $v$ let $I_v$ indicate that $v$ is selected, and assume $\Pr[I_v=1]=p$ for every $v$. Let $X=\sum_{v\in V}I_v$. Prove that $\mathbb E[X]=|V|p$ even if the selection mechanism introduces dependence among vertices.

Summary

Complexity arguments stand on four habits: measure encoding length, expose quantifiers, match the proof method to the claim, and define the probability experiment. These habits will reappear in simulations, hierarchy arguments, nondeterministic computation, and padding.

Guided practice

Task 1 — Quantifiers and constant dependence

State precisely and compare the strength of:

1. For every machine $M$ there is a constant $c_M$ such that for every input $x$, $T_M(x)\le 2^{c_M\,|x|}$.
2. There is a single constant $c$ such that for every machine $M$ and every input $x$, $T_M(x)\le 2^{c\,|x|}$.

In which statement may the constant depend on $M$? May one choose the constant after seeing $x$?

Task 2 — Three parts of a membership proof

Let $L$ be a language. State exactly what must be proved to claim $L\in\mathcal C$ when $\mathcal C$ is defined via machines with a given resource bound. Explain why a single example input is insufficient, and why an additional slow algorithm does not disprove membership.

Task 3 — Capstone: time, encoding, and probability

An algorithm receives a binary integer $N$, launches $N$ trials, and each trial has a bad event with probability at most $1/N^3$ (no independence among trials).

1. Prove the algorithm is not polynomial in the input length $n=|N|$.
2. Bound the probability of any bad event.
3. Explain when failure probability $<1$ proves existence of a good choice, and when that is not enough for an efficient algorithm.
4. Distinguish expected time from worst-case time.

Sources

• Student-summary evidence: merged course summary, pp. 1, 98, and 141. It is an image-based student summary and is used only to align emphasis and terminology, not as final authority.
• Course evidence: Semester A 2026 transcripts 1-2 for foundational course framing; no exact line locator is asserted here.
• Verification: Michael Sipser, Introduction to the Theory of Computation, 3e, pp. 3-24.
• Verification: Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach draft, pp. 9-14 and Appendix A.
• Verification: Christos Papadimitriou, Computational Complexity, pp. 1-18 and elementary probability material in Chapter 11.