cs252.md

You can't use 'macro parameter character #' in math mode

$$
\def\empty{\mathcal E}
\def\length#1{\left\lvert#1\right\rvert}
\def\accepts{,\text{accepts},}
\def\if{,\text{if},}
\def\N{\mathbb N}
$$

CS252

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Spring 2015: Theory of Computation

[TOC]

Automata

Finite automaton (DFA)

• states with conditions and starting/accepting elements
• fixed object : not allowed to depend on input size
• formal definition : $M=Q,\mathrm{\Sigma },\delta ,q_0,F$
  • $Q$ : finite set of states
  • $\mathrm{\Sigma }$ : alphabet (i.e. $0,1$ mostly)
  • $\delta (q,a):Q\times \mathrm{\Sigma }\to Q$ : transition function with $q\in Q$ and $a\in \mathrm{\Sigma }$
  • $q_0\in Q$ : starting state
  • $F\subseteq Q$ : accepting states (finite)
• extended transition function : $\hat{\delta }(q,ab)=\delta (\delta (q,a),b)$ with with $q\in Q$, $a\in {\mathrm{\Sigma }}^{\ast }$ and $b\in \mathrm{\Sigma }$
  • $\hat{\delta }(s,x)=\delta (\dots \delta (\delta (s,x_1),x_2)\dots )$ with $s$ being a starting state and $x$ being a string

Non-deterministic automaton (NFA)

• non-determinism : can be at multiple state at the same time
• powerset : $2^{{0,1}^{\ast }}=\mathrm{\varnothing },0,1,00,01,10,11,\dots$
• formal definition : $M=Q,\mathrm{\Sigma },\mathrm{\Delta },S,F$
  • $Q$ : finite set of states
  • $\mathrm{\Sigma }$ : alphabet (i.e. $0,1$ mostly)
  • $\mathrm{\Delta }(q,a):Q\times \mathrm{\Sigma }\to 2^Q$ : transition function with $q\in Q$ and $a\in \mathrm{\Sigma }$
  • $S\subseteq Q$ : starting states (finite)
  • $F\subseteq Q$ : accepting states (finite)
• extended transition function : $\hat{\mathrm{\Delta }}(A,x)$ with $A\subseteq Q$ and $x=a_1{a}_2\dots a_n\in {\mathrm{\Sigma }}^{\ast }$
  • $\hat{\mathrm{\Delta }}(A,\mathrm{\Sigma })=A$
  • $\hat{\mathrm{\Delta }}(A,xa)=\bigcup _{q\in \hat{\mathrm{\Delta }}(A,x)}\delta (q,a)$ with $x\in {\mathrm{\Sigma }}^{\ast }$ and $a\in \mathrm{\Sigma }$
• accepting criteria : $x\in L(M)⟺\hat{\mathrm{\Delta }}(S,x)\cap F\ne \mathrm{\varnothing }$ with $x\in {\mathrm{\Sigma }}^{\ast }$
• empty transition $ϵ$ : allow states flexibility
• NFA to DFA : if $N$ is a NFA then there is a DFA $M$ such that $L(N)=L(M)$
  • use transition function to generate all states unions
  • lemma : ${\hat{\delta }}_M(A,x)={\hat{\mathrm{\Delta }}}_N(A,x)\subseteq Q_N$ (by induction)
  • $Q_M=2^{Q_N}$ : but keep only the ones that are accessible
  • $\delta (T,a)=\bigcup _{q\in T}\mathrm{\Delta }(q,a)$
  • $S_M=S_N$ : all states containing NFA starting states
  • $F_M=T\in Q_M:;T\cap F_N\ne \mathrm{\varnothing }$ : all states containing NFA accepting states

Turing machines

Deterministic Turing Machine (TM)

• one tape with a head pointing on the current state
• allow to make progress in both direction
• formal definition : $M=Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,q_A,q_R$
  • $Q$ : finite set of states
  • $\mathrm{\Sigma }$ : input alphabet with $\bigsqcup \notin \mathrm{\Sigma }$
  • $\mathrm{\Gamma }$ : tape alphabet with $\bigsqcup \in \mathrm{\Gamma }$ and $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }$
  • $\delta :Q\times \mathrm{\Gamma }\to Q\times {\mathrm{\Gamma }}^{\prime }\times L,R,W$ : with ${\mathrm{\Gamma }}^{\prime }$ the letter to be write and $L,R,W$ stands for left, right and wait
  • $q_0\in Q$ : starting state
  • $q_A\in Q$ : accepting state (finite)
  • $q_R\in Q$ : rejecting state (finite)
• starting configuration : $tape=q_0{w}_1{w}_2\cdots {\bigsqcup }^{\mathrm{\infty }}$ with $q_0$ being the head
• running configuration (at any moment} : $head=UqV$ where $U=w_1\cdots w_i{w}_j$ being last character read on the tape and $V=w_k\cdots {\bigsqcup }^{\mathrm{\infty }}$ with $w_j$
• progress : $C_1\underset{M}{\overset{1}{\to }}{C}_2\underset{M}{\overset{1}{\to }}\cdots \underset{M}{\overset{1}{\to }}{C}_R$
• halts on input $w$ only
  • if $q\in q_A$, $M$ accepts $w$
  • if $q\in q_R$, $M$ rejects $w$
• describe by tape pseudocode (with subroutines)
• set of all Turing machine : countable
• multi $n$ tapes
  • $\delta :Q\times {\mathrm{\Gamma }}^n\to Q\times {\mathrm{\Gamma }}^n\times L,R,W$
  • can be reduce to a single tape by adjusting transistion function and concatenate tapes (using marker heads)
• Church thesis : no computer has more power than Turing machines
• $$ denotes the encoding of $B$ (could be a Turing machine or an automaton)
• can take the encoding of another Turing machine and run it on a specified input

Non-deterministic Turing Machine (NTM)

• multiple branch at the same time
• formal definition : $M={Q,\Sigma,\Gamma,\delta,q_0,q_A,q_R}$
  • $Q$ : finite set of states
  • $\Sigma$ : input alphabet with $\sqcup\not\in\Sigma$
  • $\Gamma$ : tape alphabet with $\sqcup\in\Gamma$ and $\Sigma\subseteq\Gamma$
  • $\delta : Q\times\Gamma\to 2^{Q\times\Gamma'\times{L,R,W}}$ : with $\Gamma'$ the letter to be write and $L,R,W$ stands for left, right and wait
  • $q_0\in Q$ : starting state
  • $q_A\in Q$ : accepting state (finite)
  • $q_R\in Q$ : rejecting state (finite)
• computation trees (deciders) : all possible combinations

Language

Regularity

• string : $\sigma\in\Sigma^*$
• empty string : $\empty$
• regular language : set of string accepted by $L(M)$
• irregular language : no $M$ such that $L(M)=A={0^n1^n:;n\ge 0}\subseteq\Sigma^*$
• complement : $\overline{L(M)}=\Sigma^*-L(M)$ by inverting accepting states (i.e. $F'=Q-F$)
• regularity for languages $A,A_1,A_2$ over
  • union : $A_1\cup A_2={\sigma:;\sigma\in A_1\lor\sigma\in A_2}$
    • $Q=Q_1\times Q_2$
    • $q_0=(q_1,q_2)$
    • $\delta((q_i,q_j), a)=(\delta(q_i,a),\ delta(q_j,a))$
    • $F=(F_1\times Q_2)\cup(Q_1\times F_2)$
  • intersection : $A_1\cap A_2={\sigma:;\sigma\in A_1\land\sigma\in A_2}$
  • concatenation : $A_1\circ A_2={\sigma_1\sigma_2:;\sigma_1\in A_1,;\sigma_2\in A_2}$
  • complement $\bar A={\sigma\in\Sigma^*:;\sigma\not\in A}$
• pumping lemma
  • if $A$ is a regular language then $\exists p\ge 0$ (called the pumping length) such that if $\sigma\in A$ and $\length{\sigma}\ge p$ then $\sigma = xyz$
    • $xy^iz\in A \forall i \ge 0$
    • $\length{xy}\le p$
    • $\length y \ge 1$
• intersection $A=B\cap C$ : if $B$ is irregular and $C$ regular, then $A$ is irregular
• set of all language $\Sigma^*$ : uncountable

Decidability

• Turing decidable language $A$ (recursive language) : if $\exists M$ (a Turing machine) such that
  • $M(w)\downarrow$ : always halts
  • $M(w)=yes\iff w\in A$ or $A=L(M)={\omega : M\accepts\omega}$
• undeciabability
  • take $A_{TM}={<M,\omega> : M\accepts\omega}$
  • assume $H(M)={<M,> : M\accepts\text{its encoding}}$ such that $H$ decide $A_{TM}$ (halts)
  • construct a decider $D(M)$ : run $H(M)$ and if $H$ accepts, $D$ rejects or if $H$ rejects, $D$ accepts
  • run $D(D)$
    • $D$ accepts $$ only if $H$ rejects $<D, >$ but that only happen when $D$ rejects $$
    • $D$ rejects $$ only if $H$ accepts $<D, >$ but that only happen when $D$ accepts $$

Recognisability

• Turing recognizable language $A$ (semi-recursivelanguage) : if $\exists M$ (a Turing machine) such that
  • if $w\in A$, $M(w)=yes$
  • if $w\not\in A$, either $M(w)\uparrow$ (loops) or $M(w)=no$
• $L$ and $\overline L$ recognizable $\iff$ $L$ dedicable
  • let $M_1$ and $M_2$ recognize $L$ and its complements
  • construct a machine $P$ that runs $M_1$ and $M_2$ in parallel
    • if $M_1$ accepts, $P$ returns $yes$
    • if $M_2$ accepts, $P$ returns $no$
  • by definition $P$ decide $L$

Reduction ${\le }_M$

• computable function : $f : \Sigma^*\to\Sigma^ *$ if there is a Turing machine which stops on input $w$ with $f(w)$ on its output tape
• Turing reductible $A\le_M B$: a language $A$ is Turing reductible to $B$ if there is a computable function such that $\forall w\in\Sigma^*$ we have $w\in A\iff f(w)\in B$

Time complexity

• worst case complexity : $t(n)$
• Big-O : $f(n)=O(g(n))\iff \exists c,n_0\text{ such that }\forall n\ge n_0; f(n)\le c g(n)$
• time complexity: let $t:\N\to\N$, for a Turing machine $M$ (that halts on all inputs) has worst-case time complexity $O(t(n))$ if $\forall w\in\Sigma^*$ we have $\length{w}=n$
• algorithms
  • $A={0^n1^n : n\ge 1 }$
    • check $0^*1^ *$, cross one $0$ and one $1$, check crosses : $O(n^2)$
    • split 0s ans 1s : $O(n)$
  • BFS/DFS : $t(n)=\length{m}\length{n}$
  • is there a cycle such that all vertices are present at least once on the cycle
    • Eulerian iff degrees of every V is even : $\in P$ (same as counting degree)
• if $t(n)$ is the time for solving on $k$-tapes, single tape implementation is in $O(t(n)\log(t(n)))$
• time complexity $1$-tape : $TIME(t(n))={L : \exists \text{ TM }M\text{ such that }M\text{ decides }L\text{ in }O(t(n))\text{ time}}$
• non-deterministic time complexity : $NTIME(t(n))$ length of longest path of computation trees of NTM
• polynomial time verifier $V(w\in L, c=PATH)$ : can verify proposition or $L\in NP$ if there is a NTM which take $n^k$ time
• Polynomial : $P=\cup_{k\ge 0} TIME(n^k)$
• Non-deterministic Polynomial : $NP={\text{all languages for which there is a polytime verifer}}=\cup_{k\ge 0} NTIME(n^k)$
• NP-Completeness : a language is said to be NP-Complete if $L\in NP$ and $\forall A\in NP;A\le_p L$
• Exponential : $EXPTIME=\cup_{k\ge 0} TIME(2^{n^k})$
• $P\subseteq NP$ but is the inverse true ?
• Cook-Levin theorem : if $SAT\in P \Rightarrow P=NP$
• NP-hardness : if finding a solution for $L$ means $P=NP$

Reduction ${\le }_P$

• polytime function : the mapping can be done in polynomial time
• polytime reduction $A\le_P B$ : a language $A$ is polytime reductible to $B$ if there is a computable and polytime function such that $\forall w\in\Sigma^*$ we have $w\in A\iff f(w)\in B$ (completeness & soundness)

Space complexity

• how much tape is used as a fonction of $n$ in the worst case
• space complexity : a language $L$ is accepted by a TM which uses $f(n)$ space on inputs of size $n$ is in $SPACE(f(n))$
• non-deterministic space complexity : a language $L$ is accepted by a NTM which uses $f(n)$ space on inputs of size $n$ is in $NSPACE(f(n))$
• $PSPACE=\cup_{k\ge 0} SPACE(n^k)$
• $NSPACE=\cup_{k\ge 0} NSPACE(n^k)$
• $NP\subseteq PSPACE \subseteq NSPACE$
• all configuration of a TM hold in less that $|\Sigma|^{n^2}\approx 2^{nk}$ : $PSPACE\subseteq EXPTIME$
• Savitch theorem : $PSPACE=NSPACE$ (NTM are powerless)
• relation between space and time complexity

Problem indexes

P

• EULERIANPATH (undirected graph) : is there a cycle such that all vertices are present at least once on the cycle ? Eulerian iff the degrees of every vertex is even

NP-Complete

• CLIQUE (undirected graph) : has a clique (complete subgraph) of size $k$
• **3SAT : is there an assignment that satifies $(x_1\vee \overline{x_2}\vee x_3)\wedge\cdots\wedge(x_4\vee x_2\vee \overline{x_3})$ where there is $n$ vars and $m$ clauses
• SAT : 3SAT but without 3-place clauses constrain
• VERTEXCOVER : has a vertex cover (i.e. all edges are reached) of size $k$
• SUBSETSUM
• HAMPATH (directed graph) : is there a hamiltonian path (i.e. visit each vertex only once) from $s$ to $t$

Co-NP

• $\overline{HAMPATH}$ : no polytime verfier

Language indexes

Regular

Non-regular

• $A={0^n1^n : n\ge 1 }$
• $B={\sigma : \text{# of 0s = # of 1s}}$ : contains $A$ under intersection

Decidable

• $A={<D, w> : \if D\accepts w}$
• $B={ : L(D)\not=\emptyset}$
• $EQ={<D_1,D_2> : D_1,D_2\text{ are DFAs }\wedge L(D_1)=L(D_2)}$ : check for empty symmetric difference

undecidable but recognisable

• $A_{TM}={<M,\omega> : M\accepts\omega}$
• $HALT={<M,w> : M(w)\downarrow }$
• $REG={ : L(M)\text{ is regular}}$

unrecognisable

• $\overline{A_{TM}}={<M,\omega> : M\text{ doesn't accept }\omega}\cup{\text{bad encodings}}$