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}}$ .

In other words, we will construct 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 (complexity class) [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? 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”. Come up with a language that the “fast” Turing machines cannot possibly decide, that is decidable by a “slow” machine.

A 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 and P.

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

NP and Time Complexity [cpsc/NP-complexity]

NP is very important! Contains a large about of natural problems.

ex. Hamilton path, 3COLORGRAPH, graph isomorphism, satisfiable boolean formulas

Many problems in NP have “identical complexity”, i.e., are complete. (We’ll talk about this later.)

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!

Recall:

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

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 3. NTIME(t(n)) [NTIME-tn]

NTIME(𝑡(𝑛))={language𝐿:∃NTM𝑀thatdecides𝐿in time𝑂(𝑡(𝑛))}

NP (complexity class) [cpsc/NP]

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

Obvious: P $\subset$ NP

Example. 3colormap $\in$ NP

Let’s prove that 3colormap is in NP.

Proof: Design a nondeterministic Turing machine to decide 3colormap in polynomial time.

Iterate through vertices
Nondetermistically pick a color for each vertex (a “lucky guess”)
Check all pairs of neighbors to see if they are the same color
If so reject, otherwise accept

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. Why?

Because 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

Claim: Clique $\in$ Np (complexity class) ( $\text{CLIQUE} = \left\{ {\left\langle {G,K} \right\rangle:G\ \text{contains a clique of size}\ k} \right\}$ )
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, then all of them are in P. NP-completeness!

Problem. SAT [SAT]

SAT is the canonical problem in NP (like how $A_{\text{TM}}$ was our canonical undecidable problem).

$\text{SAT} = \left\{ {\left\langle \varphi \right\rangle:\varphi\ \text{is a Boolean formula for which there exists a satisfying truth assignment}} \right\}$

e.g. $\varphi\left( {x_{1},x_{2},x_{3},x_{4},x_{5}} \right) = \left( {\left( {\left( {x_{1} \vee x_{2}} \right) \land \left( {x_{1} \vee \neg x_{3} \vee x_{4}} \right)} \right) \vee \neg\left( {x_{2} \land x_{3}} \right) \vee x_{4}} \right) \land \neg x_{5}$
- helpful to visualize with a tree diagram

A satisfying truth assignment is an assignment of true/false to each variable so that the whole formula is true.

Problem. 3SAT [3SAT]

Definition 1. Conjunctive Normal Form [cnf]

A problem is in conjunctive normal form (CNF) if it is a product of sums: i.e. an AND of ORs.

Example. $\text{3SAT}$

$\text{3SAT} = \left\{ {\left\langle \varphi \right\rangle:\varphi\ \text{is a Boolean formula in CNF with 3 literals per clause for which there exists a satisfying truth assignment}} \right\}$

e.g. $\left( {x_{1} \vee \neg x_{2} \vee x_{3}} \right) \land \left( {x_{5} \vee x_{4} \vee \neg x_{2}} \right) \land \left( {\neg x_{4} \vee x_{1} \vee x_{3}} \right) \land \left( {\neg x_{3} \vee x_{2} \land \neg x_{1}} \right)$

Definition 4. Polytime Reduction [polytime-reduction]

Definition 1. Polytime Computable [polytime-computable]

For some function $f:\Sigma \ast \rightarrow\Sigma \ast$ , it is polytime computable if there exists a Turing machine that when given $x$ as input terminates with $f(x)$ on the tape and runs in time $\text{poly}\left( |x| \right)$ .

Let $A,B \subseteq \Sigma \ast$ (Let $A$ and $B$ be languages). $f$ is a polytime reduction from $A$ to $B$ if:

$f$ is a polytime computable function
$x \in A\Rightarrow f(x) \in B$ ( $f(A) \subseteq B$ )
$x \notin A\Rightarrow f(x) \notin B$ ( $f(A^{\_} \subseteq B^{\_}$ )

We then may say $A\underset{P}{\leq}B$ .

…helpful image…

Example. Polytime Reduction

Suppose $A = \left\{ {0^{n}10^{n}:n \geq 0} \right\}$ , and $B = \left\{ {1^{n}01^{n}:n \geq 0} \right\}$ . Claim: $A\underset{P}{\leq}B$

What does this mean? It means there exists some function that can take a string, map it, and manipulate it so that if $x \in A$ , then $x \in B$ , and same for converses.

Proof.

Let $f$ be the function that flips the bits of its input. Then, we’re done.

$x \in A\Rightarrow f(x) \in B$
$x \notin A\Rightarrow f(x) \notin B$
$f(x) \in B\Rightarrow x \in A$
$x \in A\Leftrightarrow f(x) \in B$
Note: these do not need to be bijections!
- A reduction that simply sends all satisfiable inputs to 0 is fine.

Reductions are helpful!

Method: find a way to map:
- yes-instances of $P_{1}$ to yes-instances of $P_{2}$
- no-instances of $P_{1}$ to no-instances of $P_{2}$
Notation: $P_{1}\underset{P}{\leq}P_{2}$
Logic: if $P_{2}$ is easy, $P_{1}$ is easy
Contrapositive: if $P_{1}$ is hard, $P_{2}$ is hard

Theorem.

If $A\underset{P}{\leq}B$ and $B \in P$ , then $A \in P$ .

There is a polytime Turing machine N that decides $B$ .
There is a polytime reduction $f$ from $A$ to $B$ .

Proof.

We want a Turing machine $M$ that decides $A$ in polynomial time.

On input $x$ : compute $z = f(x)$ and then simulate $N$ on input $z$ . Accept iff $N$ accepts.
If $x \in A\Rightarrow f(x) \in B\Rightarrow N\ \text{accepts}$ .
If $x \in A^{\_}\Rightarrow f(x) \notin B\Rightarrow N\ \text{rejects}$ .

Question. If we know $A$ reduces to $B$ and $B$ is in $\text{NP}$ , is $A$ in $\text{NP}$ ?

Answer. Yes, $\text{P}$ is a subset of $\text{NP}$ . Mind the direction!

When we talked about Turing machines, we had a notion of what it meant to be hard: undecidability. But now we’re talking about NP. So which problems in NP are hard?

Maybe $\text{P} = \text{NP}$ , and so all problems in NP are easy.

Definition 5. NP-Hardness [NP-hard]

A language L is NP-hard if it is at least as hard as every problem in NP, i.e. $A\underset{P}{\leq}L,\forall A \in \text{NP}$ .

There’s nothing in this definition that’s really specific for NP. We could switch it out for other complexity classes if we’d like.

Note: we don’t require our language to be in NP! $A_{\text{TM}}$ is NP-hard.

Definition 1. NP-Completeness [NP-complete]

A language $L$ is NP-complete if $L$ is NP-hard and $L \in \text{NP}$ .

Theorem. Cook-Levin Theorem

SAT is NP-complete.

Corollary.

3SAT is also NP-complete.

Theorem.

If B is NP-complete, $C \in \text{NP}$ , and $B\underset{P}{\leq}C$ , then $C$ is NP-complete.

Proof.

Need to show: $A\underset{P}{\leq}C,\forall A \in \text{NP}$
We know $A\underset{P}{\leq}B$ , i.e. you can solve $A$ in terms of $B$ .
- So $\exists$ a polytime computable $f:x \in A\Leftrightarrow f(x) \in B$ .
We know $B\underset{P}{\leq}C$ : $\exists$ a polytime computable $g:y \in B\Leftrightarrow g(y) \in C$
Let $h:\Sigma \ast \rightarrow\Sigma \ast$ be $h(x) = g\left( {f(x)} \right)$ . This is polytime computable.
- Has the properties: $x \in A\Leftrightarrow f(x) \in B\Leftrightarrow g(f(x) \in C$ .

Problem. CLIQUE [CLIQUE]

Given $G = \left( {V,E} \right)$ and $k$ , does there exist $U \subseteq V$ with $|U| \geq k$ such that $\left\{ {u,v} \right\} \in E$ for all distinct vertices $u,v \in U$ ?

$\text{CLIQUE} = \left\{ {\left\langle {G,K} \right\rangle:G\ \text{has a clique of size}\ k} \right\}$

No specification on size: in our example above, there are cliques of size 0 through 3

Theorem.

CLIQUE is NP-complete: i.e. CLIQUE is NP-hard, and CLIQUE is in NP.

Proof.

CLIQUE is in NP: because there exists a verifier that can check a possible clique in polytime.

CLIQUE is NP-hard: because 3SAT (known NP-hard problem) reduces to CLIQUE. How can we do that?

Proof. $\text{3SAT}\underset{P}{\leq}\text{CLIQUE}$ (reduction)

$x \in \text{3SAT}$ maps to $f(x) \in \text{CLIQUE}$

If $x = \left\langle \varphi \right\rangle$ where $\varphi$ is a satisfiable 3CNF formula, then $f(x) = \left\langle {G,k} \right\rangle$ where $G$ has a clique of size $k$ .

$x \notin \text{3SAT}$ maps to $f(x) \notin \text{CLIQUE}$

If $x = \left\langle \varphi \right\rangle$ where $\varphi$ has no satisfiable assignments, then $f(x) = \left\langle {G,k} \right\rangle$ where $G$ has no clique of size $k$ .
junk can map to junk

We can show 3SAT can be solved by finding a clique of size $k$ .

Connect every vertex in a block to every other vertex that is not its inverse.
Then, every clique of size $k$ is a possible satisfiable assignment.
We can’t have $x_{i}$ and $x_{i}^{\_}$ both being true: which is represented by no connecting edges.

We still need to “decode” $f(x) \in B$ to $x \in A$ … i.e. $f(x) \in \text{CLIQUE}\Rightarrow x \in \text{3SAT}$ .

Let $U$ be a clique of size $k$ . We must divy it up so that there is exactly one vertex in each group.
Given a $f(x) \in \text{CLIQUE}$ constructed from a $\text{3SAT}$ problem, then we find a satisfying $x \in \text{3SAT}$ .

Aside: suppose we want to ensure there is a clique of at least size $k - 1$ . We can make a separate, disconnected clique of $k - 1$ vertices. What’s this useful for? Don’t know yet…

When designing a reduction: if you want to show that your reduction is correct: you need to show that

f is polytime computable
$x \in A\Rightarrow f(x) \in B$
$f(x) \in B\Rightarrow x \in A$ (the converse)
or, $x \notin A\Rightarrow f(x) \notin B$ (the inverse)

In a reduction, it’s more typical to show $x \in A\Rightarrow f(x) \in B$ (often straightforward).

Often want to “decode” $f(x) \in B$ to obtain $x \in A$ .

Theorem 3. Cook-Levin Theorem [cook-levin]

Theorem.

SAT is in NP (you can construct a verifier that runs in polynomial time)

Corollary.

SAT is NP-complete.

Proof.

To prove this, we must show that $\forall A \in \text{NP},A\underset{P}{\leq}\text{SAT}$ .

What do we know about $A$ ? It’s in NP, i.e., there is a nondeterministic Turing machine that decides $A$ in polytime

Idea: given a deterministic Turing machine $M$ and an input $W$ , we can create a circuit $f$ such that $M$ accepts $w$ if and only if $f$ evaluates to true.

That’s great, but we really want to construct it for a nondeterministic Turing machine $M$ : how can we do that?

Given $M$ and an input $w$ , construct a boolean formula $f$ with variables as inputs such that $M$ accepts $w$ if and only if $f$ is satisfiable.
i.e. the nondeterminism is each permutation of the variables, then it’s deterministic to satisfy it

Recall: Behavior of a deterministic Turing machine

Start = Config(1)
Config(2) = …
Config(3) = …
Config(i) uniquely determines Config(i+1)
The total amount of configurations we have to look at is $n^{k}$ , and the total amount of tape we have to look at is also $n^{k}$ .

Simulating a Turing machine with a tableau [cpsc/tm-tableau]

Main idea: an algorithm can be converted to a Boolean circuit

…table…

M accepts w if and only if the tableau can be filled such that:

The first row is the starting configuration of M on input w
$\left( {i + 1} \right)^{\text{st}}$ configuration follows from the $i^{\text{th}}$ configuration
Eventually reach an accepting configuration

So how can this tableau be converted into a boolean formula? We’ll come up with some boolean variables to represent what is happening in the cells.

Let $\text{cell}\left\lbrack {i,j} \right\rbrack$ refer to the according tableau entry.

Note: row i: time step, column j: head position, $i,j \leq n^{k}$
Our cell entries are not boolean values: but we still want to encode them as such!
Create boolean variables $x_{i,j,s}$ where $i,j \leq n^{k}$ and $s \in \gamma \cup Q$
$\text{cell}\left\lbrack {i,j} \right\rbrack = s\Leftrightarrow x_{i,j,s} = \text{true} \land x_{i,j,s} = \text{false}\ \forall s \neq s$

For a nondeterministic Turing machine:

The same table as the deterministic Turing machine:
only the $\left( {i + 1} \right)^{\text{st}}$ configuration follows from the $i^{\text{th}}$ configuration using some nondeterministic choice

$\varphi = \varphi_{\text{cell}} \land \varphi_{\text{start}} \land \varphi_{\text{move}} \land \varphi_{\text{accept}}$

$\varphi_{\text{cell}} = \land_{i,j}\left( {\vee_{s \in \Gamma \cup Q}\left( {x_{i,j,s} \land \neg\left( {\vee_{t \neq s}x_{i,j,t}} \right)} \right)} \right)$
$\varphi_{\text{start}} = x_{1,1,\#} \land x_{1,2,q_{0}} \land x_{1,3,w} \land x_{1,4,w}\ldots$
$\varphi_{\text{accept}} = \vee_{i,j}x_{i,j,q_{\text{accept}}}$ : check if any cell is accepting

Window[i,j]: six cells of the table (six cells is convenient: 3x2, we need three to read the current, state, and next items)

i.e. the window is size 3x2 because that’s exactly what we need to check that it is valid

$\varphi_{\text{move}} = \land_{1 \leq i \leq n^{k} - 1,1 \leq j \leq n^{k} - 2}\left( {\text{Window}\left\lbrack {i,j} \right\rbrack\ \text{is legal}} \right)$

note: pull examples, when there is no head the last two columns cannot change

… online lecture …

Definition 6. Probabilistic Turing machine [prob-turing-machine]

A computation model that begins with a tree. When you reach a branch, you flip a coin!

We can define complexity classes based on the probability of reaching accept/reject leaves.

Definition 1. Randomized Polynomial Time [RP]

The following are equivalent:

$L \in \text{RP}$ (Randomized Polytime) if there is a probabilistic Turing machine that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ , and has a greater than or equal to 50% chance of reaching an accepting leaf.
- $L \notin \text{RP}$ if the probabilistic Turing machine has a 0% chance of reaching an accepting leaf. (must reach reject state)
Algorithm’s Output Accept Reject

Correct Output

Accept $\geq 50\%$ / true positive $\leq 50\%$ / false negative

Reject 0 / false positive 1 / true negative
$L \in \text{RP}$ if there is a PTM that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ and has behavior:
- $x \in L$ : $\text{Pr}\left( \text{accept} \right) \geq 50\%$
- $x \notin L$ : $\text{Pr}\left( \text{reject} \right) = 100\%$
$L \in \text{RP}$ if there exists a deterministic polytime TM V such that:
- $x \in L$ : for at least half of all $y$ with $|y| = \text{poly}\left( |x| \right)$ , $V\ \text{accepts}\ \left( {x,y} \right)$
- $x \notin L$ : for all y with $|y| = \text{poly}\left( |x| \right)$ , $V\ \text{rejects}\ \left( {x,y} \right)$

Question. Why is RP useful?

Answer. Because we can build things that compute in RP, but we cannot easily simulate NP.

…useful picture…

If there was an NP-complete language in RP, then RP would equal NP.

$L \in \text{NP}$ if there is a TM that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ and has behavior: $\text{Pr}\left( \text{reaching accept} \right) > 0$

Definition. co-RP

$L \in \text{coRP}$ if there is a PTM that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ , and has the following behavior:

$x \in L$ (strings in the language) have a 100% chance of being accepted
$x \notin L$ have at least or equal to 50% chance of being rejected

Example. A Probabilistic Puzzle

Let $a = \left\lbrack {a_{1},a_{2},a_{3},\ldots a_{n}} \right\rbrack$ be a vector of $n$ bits.

There are two possibilities:

$a$ is all zeros
exactly half of $a$ are zeros

Question. How many bits must you look at to tell?

Answer.

Non-probabilistically: n/2 + 1
Probabilistically: just one!

Definition 2. Bounded-error Probabilistic Polynomial Time [BPP]

$L \in \text{BPP}$ (Bounded-error Probabilistic Polytime) if there is a probabilistic Turing machine that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ and has behavior:

$x \in L$ if the probability of accepting is greater than $\frac{2}{3}$
$x \in L$ if the probability of rejecting is greater than $\frac{2}{3}$
( $\frac{2}{3}$ is arbitrary: we just need $\frac{p}{q} > \frac{1}{2}$ )

Correct Output / Algorithm’s Output	Accept	Reject
Accept	$\geq \frac{2}{3}$ / true positive	$\leq \frac{1}{3}$ / false negative
Reject	$\leq \frac{1}{3}$ / false positive	$\geq \frac{2}{3}$ / true negative

…helpful diagram…

Definition 3. Amplification [amplification]

Modifying the definition of $\text{RP}$ a little bit: $L \in \text{RP}(p)$ if there is a PTM that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ and has behavior:

$\text{Pr}\left( \text{reaching accept} \right) \geq p$
$\text{Pr}\left( \text{reaching reject} \right) = 1$

Example. Claim: $\text{RP}\left( \frac{1}{2} \right) = \text{RP}\left( \frac{3}{4} \right)$

Proof.

Let $L \in \text{RP}\left( \frac{1}{2} \right)$ . There exists PTM $M$ such that $x \in L:P\left( {M\ \text{accept}\ x} \right) \geq \frac{1}{2}$ , $x \notin L:\text{Pr}\left( {M\ \text{rejects}\ x} \right) = 1$ .

Let $N$ be the Turing machine on input $x$

Run $M$ on input $x$
Run $M$ on input $x$
if either accepted, then accept
else reject

Advertisement: take CPSC 436R! Nick Harvey’s other course, on Randomized Algorithms

Definition 7. Chemoff Bound [chemoff-bound]

A Chemoff Bound will let us assert that $\text{BPP}\left( \frac{2}{3} \right) = \text{BPP}(0.99)$ .

	Algorithm’s Output	Accept	Reject
Correct Output
Accept		$\geq 50\%$ / true positive	$\leq 50\%$ / false negative
Reject		0 / false positive	1 / true negative