Complexity Theory

Complexity Classes

Definition

Def Complexity Classes

• $\mathbf{DTIME}(t(n))=\{L\mid \exists \text{det.TM decides }L\text{ in }o(t(n))\text{ time}\}$
• $\mathbf{NTIME}(t(n))=\{L\mid \exists \text{ndet.TM decides }L\text{ in }o(t(n))\text{ time}\}$
• $\mathbf{DSPACE}(t(n))=\{L\mid \exists \text{det.TM decides }L\text{ in }o(t(n))\text{ time}\}$
• $\mathbf{NSPACE}(t(n))=\{L\mid \exists \text{ndet.TM decides }L\text{ in }o(t(n))\text{ time}\}$
  They follows that
• $\mathbf{P}={\cup }_{k\in \mathbb{N}}\mathbf{DTIME}(n^k)$
• $\mathbf{NP}={\cup }_{k\in \mathbb{N}}\mathbf{NTIME}(n^k)$
• $\mathbf{PSPACE}={\cup }_{k\in \mathbb{N}}\mathbf{DSPACE}(n^k)$
• $\mathbf{NPSPACE}={\cup }_{k\in \mathbb{N}}\mathbf{NSPACE}(n^k)$
• $\mathbf{expTIME}={\cup }_{k\in \mathbb{N}}\mathbf{DTIME}(2^{n^k})$
• $\mathbf{expSPACE}={\cup }_{k\in \mathbb{N}}\mathbf{DSPACE}(2^{n^k})$
• $\mathbf{NexpTIME}={\cup }_{k\in \mathbb{N}}\mathbf{NTIME}(2^{n^k})$
• $\mathbf{NexpSPACE}={\cup }_{k\in \mathbb{N}}\mathbf{NSPACE}(2^{n^k})$

Alternative definition for $\text{NP}$: a problem is in $\text{NP}$ if we have a polynomial time verification algorithm with polynomial size certificates/proofs.

Proposition

Prop

• $\mathbf{P}\subseteq \mathbf{PSPACE}$ and $\mathbf{NP}\subseteq \mathbf{NPSPACE}$.
• $\mathbf{expTIME}\subseteq \mathbf{expSPACE}$ and $\mathbf{NexpTIME}\subseteq \mathbf{NexpSPACE}$.
• $\mathbf{P}\subseteq \mathbf{NP}$ and $\mathbf{expTIME}\subseteq \mathbf{NexpTIME}$.
• $\mathbf{PSPACE}\subseteq \mathbf{NPSPACE}$ and $\mathbf{expSPACE}\subseteq \mathbf{NexpSPACE}$.

Theorem

Thrm Savitch’s Theorem
$\mathbf{PSPACE}=\mathbf{NPSPACE}$ and $\mathbf{expSPACE}=\mathbf{NexpSPACE}$.

Reductions

Definition

Def Polytime-Computable
$f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ is a polytime-computable function if some polynomial time Turing Machine $M$ exists that halts with just $f(w)$ on its tape, when started on any input $w\in {\Sigma }^{\ast }$.

Definition

Def Polynomial Time Mapping-Reducible
$A\subseteq {\Sigma }_1^{\ast }$ is polynomial time mapping-reducible to $B\subseteq {\Sigma }_2^{\ast }$, written $A{\le }_{p}B$, if a polytime-computable function $f:{\Sigma }_1^{\ast }\to {\Sigma }_2^{\ast }$ exists. We also say it is a reduction from $A$ to $B$.

Definition

Def Reduction
A reduction is a polytime-computable map $r:A\to B$ where $A\subseteq {\Sigma }_1^{\ast }$ and $A\subseteq {\Sigma }_1^{\ast }$ such that $w\in A⟺r(w)\in B$
e.g. Reduction from ODD to EVEN: $r(k)=k+1$, so $k$ is odd iff $r(k)$ is even.

Completeness & Hardness

Definition

Def $\mathbf{NP}\text{-Hard}$
The definition of $\mathbf{NP}\text{-Hard}$ set is $\mathbf{NP}\text{-Hard}=\{L\mid \forall A\in \mathbf{NP},A{\le }_{p}L\}$

Definition

Def $\mathbf{NP}\text{-Complete}$
A language $L$ is said to be $\mathbf{NP}$-complete if $L\in \mathbf{NP}$ and $L\in \mathbf{NP}\text{-Hard}$. And $\mathbf{NP}\text{-Complete}$ is the set of such languages.

Proposition

Prop $\mathbf{NP}$-complete problems are the hardest ones in $\mathbf{NP}$.

Theorem

If $L\in \mathbf{NP}\text{-Hard}$ and $L{\le }_{p}M$, then $M\in \mathbf{NP}\text{-Hard}$.

Corollary

If $L\in \mathbf{NP}\text{-Complete}$ and $L{\le }_{p}M$ for some $M\in \mathbf{NP}$, then $M\in \mathbf{NP}\text{-Complete}$.

Comment

List of known $\mathbf{NP}$-complete problems:

• SAT (first problem proved $\mathbf{NP}\text{-Hard}$) and 3-SAT
• Graph-Colorability and 3-Graph-Colorability
• Independent Set and Vertex Cover
• Hamiltonian path
• Traveling Salesman Salesman Problem