Complexity theory

Definition 378.1(Turing machine).

A deterministic Turing machine $M$ is defined as $(\Sigma ,Q,\delta )$ where

1. $\Sigma$ is the tape alphabet
2. $Q$ is a finite set of states with $q_{\text{start}},q_{\text{accept}},q_{\text{reject}}$.
3. transition function $\delta :{\Sigma }^{k+1}\times Q\to {\Sigma }^k\times Q\times \{L,R{\}}^{k+1}$.
   Note that the TM a read-only input tape.

We define time to be the number of transitions a TM goes through from start to halt.
We say $M(x)=1$ iff $M$ halts on $x$ in $q_{\text{accept}}$.

Definition 378.2(Time complexity).

For a TM $M$,

$$\begin{array}{r}{T}_M(n):=\underset{x\in \{0,1{\}}^{\ast },|x|=n}{\max }{T}_M(x),\end{array}$$

where $T_M(x)$ is the time taken for $M$ to halt on $x$.

Alphabet reduction: For a TM $M$ with alphabet $\Sigma$, there is an equivalent TM $\hat{M}$ with alphabet $\{0,1,▹,\_\}$ (where the last two are ‘start’ and ‘blank’ symbols respectively) such that $\hat{M}$ runs in $O(\lceil {\log }_2|\Sigma |\rceil T_M(n))=O(T_M(n))$.

Tape reduction: For a $k$-tape TM $M$, there is a 2-tape TM $\tilde{M}$ such that $\tilde{M}$ decides the same language and takes time $O(T_M(n)\log T_M(n))$.

[!Theorem] Universal Turing Machine
There is a TM $U$ and an encoding scheme for TMs such that $U$ takes $⟨⟨M⟩,x,1^t⟩$ as input, simulates $M$ on $x$ for $t$ steps, and produces $M(x)$ in time $O(t\log t)$ iff $M$ decides $x$ in $t$ time.

A nondeterministic halting TM is one which halts on each computation path for each input. Time complexity is defined as

$$\begin{array}{rl}& \\ & T_M(n)=\underset{|x|=n}{\max }{T}_M(x)\\ & T_M(x):=\underset{\text{all comp paths p}}{\max }\text{time taken on }x\text{ along }p\end{array}$$

We will assume that all TMs are of this variety.

[!Definition] Complexity classes
$\text{DTIME}(T(n))=\{L\subseteq \{0,1{\}}^{\ast }:\exists \text{DTM }M\text{ that decides }L\text{ in }O(T(n))\text{ time}\}$.
$\text{NTIME}(T(n))=\{L\subseteq \{0,1{\}}^{\ast }:\exists \text{NDTM }M\text{ that decides }L\text{ in }O(T(n))\text{ time}\}$.
$x\in L$ iff there exists some path in the execution tree of $M$ which accepts.

$$\begin{array}{rl}& P=\bigcup _{c⩾1}\text{DTIME}(n^c)\\ & NP=\bigcup _{c⩾1}\text{NTIME}(n^c)\end{array}$$

If $L\in P$, then $\overline{L}\in P$. If $L\in NP$, then $\overline{L}\in \text{co-NP}$. We do not know whether $\text{NP}=\text{co-NP}$.

Observe that a NDTM with time complexity $O(n^c)$ can be simulated by a DTM with time complexity $O(2^{n^c})$, since it has to check every path of a computation tree of height $O(n^c)$.

NPSACE and PSPACE definitions

---

Many-one reductions

$L_1{⩽}_m^{\text{poly}}{L}_2$ implies

1. If there is a polytime algo to determine membership in $L_2$, then there is a polytime algo to determine membership in $L_1$.
2. If there does not exist a polytime algo for $L_1$, then there does not exist a polytime algo for $L_2$.

Lemma 378.3(Lemma).

Let $L_1{⩽}_m^{\text{poly}}{L}_2$. If $L_2\in \text{NP}$, then $L_1\in \text{NP}$.

${⩽}_m^{\text{poly}}$ is a transitive relation.

Definition 378.4(Definition).

$L\subseteq {\Sigma }^{\ast }$ is NP-hard if forall $L^{\prime }\subseteq {\Sigma }^{\ast }$ such that $L^{\prime }\in \text{NP}$, $L^{\prime }{⩽}_m^{\text{poly}}L$. If, additionally, $L\in \text{NP}$, then $L$ is said to be NP-complete.

[!Theorem] Cook-Levin
$\text{SAT}$ is NP-complete.

encode verifying computation histories as a SAT instance.