Complexity

Running time

• The running time (or time complexity) of a decider DTM $M$ is the function $f:\mathbb{N}\to \mathbb{N}$, where $f(n)$ is the maximum number of steps that $M$ takes on any input of length $n$.

• The running time of a decider NTM $M$ is the function $f:\mathbb{N}\to \mathbb{N}$, where $f(n)$ is the maximum number of steps that $M$ uses on any branch of its computation on any input of length $n$.

• If $f$ is the running time of $M$, we say that $M$ runs in time $f(n)$, and we say that $M$ is a $f(n)$-time TM.

• A verifier for a language $L$ is a TM $V$ such that $L=\{w\mid \exists c:V(⟨w,c⟩)=\text{accept}\}$.

  • Let $L$ be a language with verifier $V$.
    • A certificate (or proof) for a string $w\in L$ is a string $c$ such that $V(⟨w,c⟩)=\text{accept}$.
    • The running time of $V$ is
      • (e.g. A polynomial time verifier is a verifier that runs in polynomial time, and a language is polynomially verifiable if it has a polynomial time verifier.)

• A function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ is a polynomial time computable function if there exists a polynomial time TM $M$ such that for every $w\in {\Sigma }^{\ast }$, $M$ halts with $f(w)$ on its tape.

Complexity classes

• ((deterministic) time complexity class) $\mathsf{TIME}(t(n))=\{L\mid L\text{ is decidable by an }O(t(n))\text{-time TM}\}$.

  • (Also denoted $\mathsf{DTIME}(t(n))$).

• (nondeterministic time complexity class) $\mathsf{NTIME}(t(n))=\{L\mid L\text{ is decidable by an }O(t(n))\text{-time NTM}\}$.

• (examples: $\mathsf{TIME}(n^2)$ is the set of languages decidable by a TM that runs in $O(n^2)$ time. $\mathsf{NTIME}(\log n)$ is the set of languages decidable by a NTM that runs in $O(\log n)$ time.)

• The complexity class $\mathrm{P}$ (polynomial time) is defined as $\mathrm{P}=\bigcup _{k\in \mathbb{N}}\mathsf{TIME}(n^k)$ (i.e. the set of languages decidable by a polynomial-time TM)

  • (Also denoted $\mathsf{PTIME}$, or $\mathsf{DTIME}(n^{O(1)})$).

• The complexity class $\mathrm{NP}$ (nondeterministic polynomial time) can be defined by the two equivalent definitions:

  • $\mathrm{NP}=\bigcup _{k\in \mathbb{N}}\mathsf{NTIME}(n^k)$ (i.e. the set of languages decidable by a polynomial-time NTM).
  • (7.20) $\mathrm{NP}=\{L\mid L\text{ is decidable by a polynomial time verifier}\}$.

• $\mathrm{P}\subseteq \mathrm{NP}$.

• $\mathrm{EXPTIME}=\bigcup _{k\in \mathbb{N}}\mathsf{TIME}(2^{n^k})$ is the time complexity class of languages decidable by an exponential time TM.

• $\mathrm{NP}\subseteq \mathrm{EXPTIME}$.

• Exmaples of languages in $\mathrm{NP}$:

  • Clique: $\text{CLIQUE}=\{⟨G,k⟩\mid G\text{ is an undirected graph with a }k\text{-clique}\}$.
  • Subset sum problem (SSP): $\text{SUBSET-SUM}=\{⟨S,k⟩\mid S\text{ is a multiset of integers and there exists }T\subseteq S\text{ s.t.}\sum _{x\in T}x=k\}$.

• A language $A$ is polynomial time many-one reducible (or polynomial time (mapping) reducible) to a language $B$, denoted $A{\le }_{P}B$, if there exists a polynomial time computable function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ such that for every $w\in {\Sigma }^{\ast }$, $w\in A⟺f(w)\in B$. (in such case $f$ is called the polynomial time reduction of $A$ to $B$).

  • If $A{\le }_{P}B$ and $B\in \mathrm{P}$, then $A\in \mathrm{P}$.
  • If $A{\le }_{P}B$ and $B{\le }_{P}A$, then $A$ and $B$ are polynomial time equivalent, denoted $A{\equiv }_{P}B$.
    • ${\equiv }_P$ is an equivalence relation on $\mathrm{NP}$.
    • $\mathrm{P}\setminus \{\varnothing ,{\Sigma }^{\ast }\}$ is an equivalence class of ${\equiv }_P$.

• A language $B$ is $\mathrm{NP}$-complete if:

  • $B\in \mathrm{NP}$.
  • For every language $A\in \mathrm{NP}$, $A{\le }_{P}B$.

• (7.35) If $B$ is $\mathrm{NP}$-complete and $B\in \mathrm{P}$, then $\mathrm{P}=\mathrm{NP}$.

• (7.36) If $B$ is $\mathrm{NP}$-complete and $B{\le }_{P}C$ for $C$ in $\mathrm{NP}$, then $C$ is $\mathrm{NP}$-complete.

• If $\mathrm{P}\ne \mathrm{NP}$, then:

  • (Ladner’s theorem) $\mathrm{NP}\text{-intermediate}=\mathrm{NP}\setminus (\mathrm{P}\cup \mathrm{NP}\text{-complete})\ne \varnothing$.

• If $\mathrm{P}=\mathrm{NP}$, then:

  • $\mathrm{NP}\text{-complete}=\mathrm{P}=\mathrm{NP}$.