Computability vs. Complexity [computability-complexity]

What is the difference between this theory of computation and Turing machines, vs. complexity?

Computability-theory studies whether problems have any algorithmic solution whatsoever.

Complexity theory studies whether problems have efficient algorithmic solutions.

How much time is required?
How much space is required?
Does randomness help?

Definition 1. 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