Definition. Worst case analysis [worst-case-analysis]

Usually theorists do worst case analysis, i.e. as a function of the input length $n$ , what is the maximum amount of resources used over all inputs of length $n$ ? (note: $n$ is a commonly used variable!)

The idea here is that it’s helpful to analyze the worst case, as every input will then result in equal or better time.

Definition 1. Runtime [runtime]

Complexity theory.
1. The runtime of a Turing machine $M$ is $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ : $f(n) = \max\left( {x \in \Sigma \ast ,|x| = n} \right)$ . (the number of steps of $M$ on input $n$ until it halts) (assume $M$ is a decider for simplicity)
2. The runtime of a nondeterministic Turing machine $\text{NTM}$ on input $X$ is max-length of any root-leaf path. For deciders – no infinite paths!

Definition 2. Class [class]

Complexity theory. A class is a set of languages (or equivalently, computational problems).

Definition 3. Complexity class [complexity-class]

A complexity class is a class defined by Turing machine resource constraints.

Definition 4. TIME(t(n)) [time-tn]

$\text{TIME}\left( {t(n)} \right)$ is the class of all languages $L$ such that there exists a Turing machine with runtime $O\left( {t(n)} \right)$ that decides $L$ .

In briefer notation: $\text{TIME}\left( {t(n)} \right) = \left\{ {\text{language}\ L:\exists\ \text{TM}\ M\ \text{that decides}\ L\ \text{in time}\ O\left( {t(n)} \right)} \right\}$

Definition 1. P (complexity class) [p]

$P = \bigcup_{c > 0}\text{TIME}\left( n^{c} \right)$

Why is P a good definition for efficient computation?

Insensitive to model of computation: by the extended Church-Turing thesis, switching computational models “only” involves a polynomial slowdown
Closed under composition: can use polynomial time algorithm as a subroutine
In practice: algorithms usually can be improved. If we find an $O\left( n^{30} \right)$ time algorithm, it typically can be improved to, say, $O\left( n^{5} \right)$ time.

Example. 2COLORMAP

Let $G$ be a “map” of countries in the plane, where a coloring is valid if neighboring countries have different colors.

Question. The two color map does not work for every map. So consider it as a problem: $\text{2COLORMAP} = \left\{ {\left\langle G \right\rangle:G\ \text{has valid red/blue coloring}} \right\}$ . Is 2COLORMAP $\in$ P?

Answer. Yes! Start with an arbitrary country, set it to red, set their neighbors to blue, and continue. If there is a conflict, reject, if there is no conflict, accept.

It’s unknown if the three color map is in P. It’s known to be in EXP: $O\left( {3^{n}n^{2}} \right) \in O\left( 4^{n} \right)$

Recall: different machine models have different efficiencies: our multi-tape Turing machines were broadly more efficient than our single-tape Turing machines.

Example.

$\text{PAL} = \left\{ {ww^{R}:w \in \Sigma \ast} \right\}$

Decided by a single-tape Turing machine in $O\left( n^{2} \right)$ time
Decided by a multi-tape Turing machine in $O(n)$ time