Complexity Theory [complexity-theory]

Definition 1. Elephant Jokes [elephant-jokes]

How do you shoot a blue elephant?: With a blue elephant gun.
How do you shoot a red elephant?: Hold its trunk shut until it turns blue, then shoot it with a blue elephant gun.
How do you shoot a purple elephant?: Paint it red, hold its trunk shut until it turns blue, then shoot it with a blue elephant gun.

Elephants are much like reductions.

Definition 2. Reductions [reductions]

Say we have two problems.

Problem 1.: Shoot a red elephant.
Problem 2.: Shoot a blue elephant.

We can say that $P_{1}$ reduces to $P_{2}$ if we can design an algorithm for solving $P_{1}$ that uses $P_{2}$ . The following are equivalent:

$P_{1}\underset{T}{\leq}P_{2}$
$P_{1}$ reduces to $P_{2}$
$P_{1}$ can be solved in terms of $P_{2}$
$P_{1}$ can be solved using $P_{2}$ as a subroutine

IMPORTANT: Note the order! This is easy to flip-flop!

Given our original problems: this means that the problem of shooting a red elephant can be solved by shooting a blue elephant.

What else does this tell us?

If $P_{2}$ is easy, then $P_{1}$ is easy
If $P_{1}$ is hard, then $P_{2}$ is hard (we’ll use this idea a lot)
$P_{1}$ is no harder than $P_{2}$
$P_{2}$ is at least as hard as $P_{1}$

We can similarly talk about languages this way.

$L_{1} \leq L_{2}$ means:

deciding $L_{1}$ is no harder than deciding $L_{2}$ , or
deciding $L_{2}$ is at least as hard as deciding $L_{1}$ .

Example. Showing the Halting problem to be undecidable

Last time: $A_{\text{TM}}$ is undecidable.

$A_{\text{TM}} = \left\{ {\left\langle {M,w} \right\rangle:M\ \text{accepts}\ w} \right\}$
$\text{HALT}_{\text{TM}} = \left\{ {\left\langle {M,w} \right\rangle:M\ \text{halts on input}\ w} \right\}$

Recall: $\text{HALT}_{\text{TM}}$ is recognizable

You can create a Turing machine $U$ that takes an $\left\langle {M,w} \right\rangle$ and simulate it: if $U$ halts, our original Turing machine $M$ accepts

We want to show that $A_{\text{TM}}\underset{T}{\leq}\text{HALT}_{\text{TM}}$ . Proof by contradiction:

Suppose there is a Turing machine $R$ that decides $\text{HALT}_{\text{TM}}$ (it doesn’t exist).
We want to use $R$ to design a Turing machine $S$ that decides $A_{\text{TM}}$ . Design:
- Use $R$ to reject if the input runs forever
- Otherwise, simply simulate the input (it is now guaranteed to be decidable)
So we can, and we do, and we arrive at a contradiction: as we know there is no such decider for $A_{\text{TM}}$ .

Then as $A_{\text{TM}}$ reduces to $\text{HALT}_{\text{TM}}$ : $\text{HALT}_{\text{TM}}$ is at least as hard as $A_{\text{TM}}$ , which is undecidable. So $\text{HALT}_{\text{TM}}$ is undecidable.

Aside: reduction can go both ways! $A_{\text{TM}}$ reduces to $\text{HALT}_{\text{TM}}$ , and vice versa. There are (probably) problems that cannot be related, however.

Example. Showing that $E_{\text{TM}}$ is undecidable

We will show by reduction: by reducing $A_{\text{TM}}$ to $E_{\text{TM}}$ , i.e. show a Turing-machine for deciding $A_{\text{TM}}$ that uses $E_{\text{TM}}$ as a subroutine.

$A_{\text{TM}} = \left\{ {\left\langle {M,w} \right\rangle:M\ \text{accepts}\ w} \right\}$
$E_{\text{TM}} = \{\left\langle M \right\rangle:M\ \text{is a Turing machine and}\ L(M)\ \text{is empty}$ (i.e. $M$ accepts nothing)

Proof: Assume we have a decider $R$ that decides $E_{\text{TM}}$ . Idea: create a new Turing machine $N$ with $M,w$ hardcoded inside.

if y != w: reject
if y == w: then run $M$ on input $w$
So the language is either $w$ or $\varnothing$ .

Simulating a Turing machine $S$ on input $x$ :

if $x$ not of form $\left\langle {M,w} \right\rangle$ then reject
Construct the Turing-machine $N$ above
Run $R$ on input $N$
If $R$ accepts, then we know $M$ does not accept $w$
If $R$ accepts, $S$ rejects, and if $R$ rejects, $S$ accepts.

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

Revising the Church-Turing thesis [extended-church-turing]

The extended Church-Turing thesis is the belief that Turing machines capture our intuitive notion of what is efficiently computable. It postulates that everything we can compute in time $t(n)$ on any physical computer can be computed on a Turing machine in time $O\left( {t(n)}^{c} \right)$ , for some constant $c$ .

Is this true, does it hold? Maybe not, with newer forms of computation like quantum computers.

Definition 3. P and EXP [p-exp]

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.

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)$

Definition 2. EXP [exp]

$`\text{EXP}` = \bigcup_{k > 0}\text{TIME}\left( 2^{n^{k}} \right)$

The four color map works for all maps, so $\text{4COLORMAP} = \left\{ {\left\langle G \right\rangle:G\ \text{is a valid map}} \right\}$ .

Theorem 1. Time Hierarchy Theorem [time-hierarchy]

Question: is Exp $=$ P (complexity class)? Answer: No!

The time hierarchy theorem tells us that given an $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ that is “reasonable” where $f(n) = \Omega\left( {n\log n} \right)$ , then the $\text{TIME}\left( {f(n)} \right) \subset \text{TIME}\left( {f(n)}^{4} \right)$ .

Notably, $\text{TIME}\left( {f(n)} \right) \neq \text{TIME}\left( {f(n)}^{4} \right)$ !

Corollary.

$\text{TIME}\left( n^{c} \right) \neq \text{TIME}\left( {n^{4}c} \right)$ for any $c \geq 1$ .

Corollary.

$\text{TIME}\left( n^{c} \right) \neq \text{TIME}\left( 2^{n} \right)$ for any $c \geq 1$ .

$\text{TIME}\left( 2^{n^{k}} \right) \neq \text{TIME}$

Question. How do you prove the Time hierarchy theorem?

Answer. By diagonalization. Look at Turing machines that are “fast” and Turing machines that are “slow”.

Idea: Look at all Turing machines that run in “fast” time, and come up with a language that they cannot possibly decide.

But we want that language to be decidable by a “slow” Turing machine.

Language that is in EXP and not in P: ???

Time Complexity [time-complexity]

Where is 3COLORMAP? We know it is in Exp, and either in Np (complexity class) or in both Np (complexity class) and P (complexity class).

The Time Hierarchy theorem tells us that there is something in Exp $\smallsetminus$ P (complexity class). (why? still not clear)

Theorem 2. Certificates and Verifiers [certificates-verifiers]

NP has two main, equivalent definitions:

There exists a nondeterministic polytime TM $M$ that decides $L$ .
There exists a deterministic polytime TM $V$ and a constant $c$ s.t.:
- $L = \left\{ {x \in \Sigma \ast :\exists y \in \Sigma \ast \text{s.t.}\ |y| \leq |x|^{c} \land V\ \text{accepts}\ \left( {x,y} \right)} \right\}$
- where $x$ is the “input”, $y$ is the “certificate”, $V$ is the “verifier”

i.e. for the three color graph, give us a colored graph and we can verify it

The certificate $y$ serves as the verifier $V$ ’s substitute for nondeterminism.

Example. Verifying 3colormap

Claim: 3colormap $\in$ Np (complexity class).

$\left\{ {\left\langle G \right\rangle:G\ \text{is 3-colorable}} \right\}$
Must find a deterministic polytime TM V s.t. $\text{3COLOR} = \left\{ {x:\exists y,|y| \leq |x|^{c},V\ \text{accepts}\ \left( {x,y} \right)} \right\}$
Code for $V$ : on input $\left( {x,y} \right)$
- If $x$ not of form , where is a Graph, reject
- From $y$ , extract values $\text{color}(v) \in \left\{ {1,2,3} \right\}$ for each $v \in V$
- For every edge $\left\{ {u,v} \right\} \in E$ : if color(u) == color(v), reject
- Otherwise accept
$y$ does exist, it’s simply a valid coloring of the graph

To show correctness of $V$ , we need three things:

If $x = \left\langle G \right\rangle$ and G is 3-colorable: need $\exists y\ \text{s.t.}\ |y| \leq |x|^{c}$ and $V\ \text{accepts}\ \left( {x,y} \right)$ .
- It does exist, $y$ can be a valid 3 coloring of $G$ . Note: $|y| = O(n)$ and $|x| = \Omega(n)$
If $x \neq \left\langle G \right\rangle$ where G is 3-colorable: then no certificate $y$ should make $V$ erroneously accept.
- If $x$ not of form $\left\langle G \right\rangle$ : $v$ definitely rejects.
- If $x$ of form $\left\langle G \right\rangle$ by not 3-colorable, then $V$ must reject because it always checks that $y$ is a valid coloring.
Must check that $V$ runs in time polynomial in $|xy|$ .
- Decoding takes polytime, checking neighbors takes polytime.

Example. Proofs of equivalence of our NP definitions

Proof. $(2)\Rightarrow(1)$

Given verifier $V$ , must construct a NTM $M$ deciding $L$
Inputs to the verifier are $x$ and $y$ , with $|y| \leq |x|^{c}$
- $x$ : input string
- $y$ : certificate (like a proof that $x$ is in the language)
Code for $M$ :
- On input $x$ , nondeterministically pick $y \in \Sigma \ast$ with $|y| \leq |x|^{c}$
- Run $V$ on input $\left( {x,y} \right)$
- Accept if $V$ accepts. Reject if $V$ rejects.
i.e. Suppose $x \in L\Rightarrow\exists y\ \text{s.t.}\ V\ \text{accepts}\ \left( {x,y} \right)\Rightarrow\text{there is a leaf where}\ M\ \text{accepts}$ . If $x \notin L\Rightarrow\nexists y\ \text{s.t}.V\ \text{accepts}\ \left( {x,y} \right)\Rightarrow\nexists\ \text{leaf}$ , so $M$ does not accept $x$ .

Proof. $(1)\Rightarrow(2)$

Given an NTM $M$ , you can convert that into a verifier $V$ for $L$ .
Input to $M$ is $x$ , runtime is at most $|x|^{c}$
Idea: $V$ simulates the tree, but only on a single branch of configuration tree. $y$ specifies which branch. nondeterminism comes into play by letting us pick the correct branch.
- our nondeterminism lets us pick the correct branch: then the $c$ term is the depth of the path, which is at most polynomial
Code for $M$ :
- Simulate $M$ deterministically on input $x$ , using $y$ as the sequence of nondeterministic decisions
- Accept if $M$ accepts. Reject if $M$ rejects.

Why NP is nice [cpsc/why-np]

We’ll spend the next couple of lectures talking about Np (complexity class). Why? Nondeterministic Turing machines are ridiculously impractical!

Many problems that we’re interested in have the form $L = \left\{ {x:\exists y,|y| \leq |x|^{c},V\ \text{accepts}\ \left( {x,y} \right)} \right\}$ (where $x$ is the problem input and $y$ is the object we are seeking).

Efficient test: is $y$ a valid solution?

We showed 3COLOR $\in$ Np (complexity class).

Claim: Clique $\in$ Np (complexity class) (Clique={⟨𝐺,𝐾⟩:𝐺contains acliqueof size𝑘})
Claim: Hampath $\in$ Np (complexity class) (Hamiltonian path problem)

Np (complexity class) has lots of problems that are interesting and nice to solve, but that we don’t know of any polynomial time solution. But: if any of these problems are in P (complexity class), then all of them are in P (complexity class). NP-completeness!