\documentclass{scrartcl}
\usepackage[margin=1in, left=0.7in, right=0.7in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{subcaption}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD10} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[C]{https://louis.jachiet.com/tps.html}
\fancyfoot[R]{21 décembre 2017}
\newcommand{\DP}{\mathcal{P}}
\newcommand{\NP}{\mathcal{NP}}
\newcommand{\coNP}{\mbox{co-}\mathcal{NP}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ls}{{\mathcal{L}_\Sigma}}
\newcommand{\Lc}{{\mathcal{L}}}
\newcommand{\ml}{\mu_{\mathcal{L}}}
\newcommand{\Mn}{M_n(\Ls)}
\newcommand{\Vn}{{M_{n,1}(\Ls)}}
\newcommand{\tr}[1]{\xrightarrow{#1}}
\newcommand{\td}{\tilde{\delta}}
\newcommand{\norm}[1]{\left\lvert#1\right\rvert}
\newcommand{\code}[1]{{\langle}{#1}{\rangle}}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\newcommand*\xor{\mathbin{\oplus}}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
  question/type = exam,
  %  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%solution/print = true
}
\newtheorem{defi}{Définition}
\newcommand\myeq{\stackrel{\mathclap{\codealfont\mbox{def}}}{=}}
\setlength{\parindent}{0em}

\newcommand*\fo[1]{\tikz[baseline=(char.base)]{
                \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,trees}

\author{}
%\date{}
\title{TD10 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section{Classe AC}

\begin{defi}

Un circuit booléen avec $n$ bits d'entrée est un graphe orienté
acyclique (DAG) où les feuilles sont les $n$ nœuds représentant
l'entrée, la sortie est l'unique nœud dont le degré d'entrée est nul
et chaque nœud est soit un nœud $\land$ ou $\lor$ (qui peuvent être d'arité
quelconque) soit un nœud $\lnot$ (unaire).  Étant donné un mot $w\in
\{0,1\}^*$ de taille $n$ et un circuit dont la taille d'entrée est
$n$, on peut évaluer le circuit sur $w$ en remplaçant la $i$-ème
feuille d'entrée par $\top$ quand $w_i=1$ et $\bot$ quand $w_i=0$.
\end{defi}

\begin{defi}
  On dit qu'une \emph{famille de circuits} $(C_i)_{i\in\mathbb{N}}$ accepte un
langage $L$ quand pour chaque $n\in \mathbb{N}$, $C_n$ a $n$ bits
d'entrée et accepte $\{ w\in L \mid |w|=n \}$.
\end{defi}

\begin{defi}
On définit la classe $AC^i$ comme la classe des problèmes de décision
acceptés par un famille de circuits booléens $(C_i)_{i\in\mathbb{N}}$
dont la taille du circuit est polynomiale et dont la profondeur est de
taille $O(log(n)^i)$, c'est à dire qu'il existe $k$ tel que pour tout
$n\in \mathbb{N}$, la profondeur de $C_n$ est bornée par
$log(n^i)\times k$. La taille de $C_n$ est limitée par $P(n)$ pour un
certain $P$.
\end{defi}

\begin{question}
Justifier pourquoi l'on ne s'intéresse qu'aux circuits de taille
polynomiale (et non pas exponentielle ou illimitée).
\end{question}

\begin{solution}
Étant donné une fonction booléenne $f: \{0,1\}^n \rightarrow \{0,1\}$
on peut regarder $f^{-1}(1) = \{ (x_1, \dots, x_n) \mid f(x_1, \dots, x_n)=1 \}$.

En posant $\varphi(u_1, \dots, u_n) = \bigwedge_{u_i=1} x_i \land
\bigwedge_{u_i=0} \lnot x_i$ on a alors $\varphi(u_1,\dots,u_n)(x) = 1
\Leftrightarrow (u_1, \dots, u_n)=x$ et donc

$$f(x) = \bigvee_{(u, \dots, u)\in f^{-1}(1)} \varphi(u) $$

On peut représenter n'importe quelle fonction $f(x)$ par une formule
(et donc un circuit) de profondeur 4 (à profondeur 1 on a
$\bigvee_{u\in f^{-1}(u)}$, à profondeur 2 on a $\bigwedge_{u_i=1}
\dots \bigwedge_{u_i=0}$ et à 3 et 4 on a $x_i$ et $\lnot x_i$).
\end{solution}

\begin{question}
Montrer que le problème de décider la parité du nombre de $1$ dans
l'entrée est dans $AC^1$. Le problème de la parité correspond au
langage $\{ w\in\{0,1\}^* \mid |w|_1 \mbox{ est pair}\}$.
\end{question}

\begin{solution}
  On veut réaliser un $\xor$ de toutes les entrées $w_1, \dots,
  w_n$. Si l'on calcule $w_1 \xor (w_2 \dots ( w_{n-1}\xor w_n))$
  alors la profondeur va être $n-1$ fois celle d'un $\xor$ binaire.

  Pour simplifier on ne va travailler que sur les $n$ qui sont des
  puissances de 2 (en remplissant avec des $0$ une solution pour $n$
  peut être trouvée avec la puissance de 2 supérieure à $n$).
  
  Si $|w|>1$ on peut calculer $w'_i=w_{2i}\xor w_{2i+1}$ on ramène à
  un $w'$ de taille $|w'|=\lceil \dfrac{|w|}{2} \rceil $, la
  profondeur du calcul de $w'$ est constante et la parité du nombre de
  1 de $w$ est la même que celle de $w'$. En procédant ainsi
  récursivement en $ln(n)$ étapes on arrive à une unique valeur qui
  est la solution. La profondeur totale de ce circuit est donc $\lceil
  ln(n) \rceil$ fois la profondeur d'un unique $\xor$.
  \end{solution}

\begin{question}
  Montrer que le problème de l'addition est dans $AC^0$. Pour cela,
  exhiber une famille de circuit de profondeur bornée qui accepte les
  mots $w=abc$ avec $|a|=|b|=|c|$ et $a+b=c$ ($a$, $b$ et $c$ sont en
  représentation binaire par exemple en petit boutien).
\end{question}

\begin{solution}
  Pour tester la valeur $c_i$ il faut regarder $a_i$, $b_i$ mais aussi
  savoir s'il y a une retenue dans le calcul de $a_0 \dots a_{i-1}+b_0
  \dots b_{i-1}$. On note $r_i$ la retenue à l'étape $i$ (c'est à
  dire $a_1 \dots a_i + b_1 \dots b_i = c_1 \dots c_i r_i$)

  Si l'on regarde précisément le calcul de $a+b$ les retenues sont
  crées (i.e. $r_{i-1}=0$ mais $r_i=1$) quand $g_i=(a_i \land b_i)$ et
  transmises (i.e. $r_{i-1}=1$ et $r_i=1$) quand $p_i=(a_i \lor
  b_i)$. Donc il y a une retenue après l'étape $i$ s'il existe $j\leq i$
  tel que $tr_j^i = g_j \land p_{j+1} \land \dots \land p_{i}$.

  Donc pour savoir s'il y a une retenue en $i+1$ on calcule $r_i =
  \bigvee_j tr_j^i$ et la valeur de $c_i$ doit être égale à
  $r_i+a_i+b_i$.

  Les nœuds $p_i$ et $g_i$ sont de profondeur 1, les nœuds $tr_j^i$ de
  profondeur 2, le nœud $r_i$ est donc de profondeur $3$,
  $(a_i\xor b_i)\xor r_{i-1}=c_i$ est donc de profondeur bornée.

\end{solution}

\begin{question}
  Montrer que le problème de la multiplication est dans $AC^1$. Pour
  cela, trouver un famille de circuit qui accepte les mots $w=abc$
  avec $2|a|=2|b|=|c|$ et $a\times b=c$ ($a$, $b$ et $c$ sont en
  représentation binaire par exemple en petit boutien).
\end{question}

\begin{solution}
On a vu dans l'addition qu'on sait calculer la somme de 2 nombres. On
va proposer une méthode pour calculer la multiplication par une suite
d'additions en utilisant les formules suivantes :
  
$$mult(a_1\dots a_{2n},b) = mult(a_1\dots a_n,b) + mult(a_{n+1}\dots a_{2n},b) \times 2^n$$
$$mult(0,b) = 0$$
$$mult(1,b) = b$$


Comme la multiplication par $2^n$ est facile et que l'addition est de
profondeur constante, qu'il y a un $ln(n)$ étapes d'additions qui ont
chacune une profondeur constante donc la profondeur est $ln(n)$.

\end{solution}

\begin{question}
Montrer que tout langage régulier sur $\{0,1\}$ est $AC^1$.
\end{question}

\begin{solution}
  Soit $A=(Q,\{0,1\},\delta,q_0,F)$ un automate sur le langage
  considéré.  On note $tr(i,j,q,q')$ le circuit qui calcule si
  $\delta(q,w_i\dots w_{j-1})=q'$. Un mot $w_1\dots w_n$ est accepté
  quand $\lor_{f\in F} tr(1,n+1,q_0,f)$

  Maintenant on peut calculer $tr(i,j,q,q')$ de la façon suivante :
  $$ tr(i,j,q,q') = \lor_{q''\in Q} tr(i,(i+j)/2,q,q'')\land tr((i+j)/2,j,q'',q')$$
  $$ tr(i,i+2,q,q') = (q' = \delta(q,w_i))$$
  $$ tr(i,i+1,q,q') = (q' = q)$$

  La profondeur de ce circuit est logarithmique car à chaque étape on
  rappelle récursivement sur des segments de taille moitié avec un
  circuit de profondeur bornée (c'est un OU d'arité $|Q|$ de ET
  binaires donc borné par une profondeur $ln(|Q|)+2$ indépendante de
  $n$).
\end{solution}

\section{Classe NC}
\begin{defi}
  On note $NC^i$ la classe des problèmes de décision acceptés par une
  famille de circuits booléens $(C_n)_{n\in \mathbb{N}}$ où l'arité
  des portes $\lor$ et $\land$ est limitée à deux et où la famille de
  circuits est de profondeur $O(ln(n)^i)$ avec une taille polynomiale.
\end{defi}

\begin{question}
  Montrer que pour tout $i$ nous avons l'inégalité $NC^i\subseteq AC^i \subseteq NC^{i+1}$.
\end{question}

\begin{solution}
  Clairement, par définition $NC^i\subseteq AC^i$.

  Maintenant étant donné un circuit correspondant à une famille de
  $AC^i$ on remarque que chaque porte $\land$ ou $\lor$ a une arité
  bornée par la taille du circuit qui est polynomiale en $n$. En
  remplaçant chacune de ces portes par un arbre binaire équilibré des
  mêmes portes on obtient le résultat. Par exemple, si l'on a un nœud
  $\land(n_1, \dots, n_k)$ on créé deux nœuds $m_1=\land(n_1, \dots,
  n_{k/2})$ et $m_2=\land(n_{k/2+1}, \dots, n_k)$ et on recommence
  récursivement.
  
\end{solution}
  

\begin{question}
  Montrer que $NC^0\neq AC^0$.
\end{question}

\begin{solution}
Une famille de circuit correspondant à un problème $NC^0$ ne peut lire
qu'un nombre fini de bits et donc ne peut pas, par exemple, gérer
l'addition.
\end{solution}

\subsection{Classe TC}

\begin{defi}
La classe $TC^0$ correspond à la classe des problèmes de décision
acceptés par une famille de circuits où les portes sont $\lnot$ ainsi
que des portes de type $T_k(x_1, \dots, x_n)$ avec $T_k(x_1,\dots,
x_n)=|\{ i \mid x_i=\top\}|\ge k$
\end{defi}

\begin{question}
  Montrer que l'on peut faire les portes $\land$, $\lor$ et MAJORITÉ
  avec MAJORITÉ$(x_1, \dots, x_n)=\top$ quand la moitié de ses entrées
  sont $\top$ sans changer la profondeur de circuit.
\end{question}


\begin{solution}
  $\land (v_1, \dots, v_n)= T_n(v_1,\dots, v_n)$ et $\lor(v_1,\dots,
  v_n)=T_1(v_1,\dots,v_n)$ enfin MAJORITÉ$(v_1,\dots, v_n)=
  T_{n/2}(v_1,\dots, v_n)$.
\end{solution}

\begin{question}
  Montrer qu'à l'inverse $TC^0$ correspond aussi à la classe des
  problèmes de décision acceptés par des circuits de profondeur bornée
  avec les portes $\land$, $\lor$, $\lnot$ et MAJORITÉ (d'arités non bornées).
\end{question}

\begin{solution}
  Étant donnée un porte $T_k(x_1, \dots, x_n)$ on la transforme en la
  porte MAJORITÉ en rajoutant simplement des entrées $\top$ ou des
  $\bot$.

  Si $2k> n$, $T_k(x_1, \dots, x_n)=\mbox{MAJORITÉ}(x_1,\dots, x_n,
  t_1, \dots, t_{2k-n})$ avec $t_i=\top$.

  Si $2k<n$, $T_k(x_1,\dots, x_n) = \mbox{MAJORITÉ}(x_1,\dots, x_n,
  b_1, \dots, b_{n-2k})$ avec $b_i=\bot$.

  (les portes $\lor$ et $\land$ sont donc inutiles)
\end{solution}

\begin{question}
  Montrer $TC^0\subseteq NC^1 $
\end{question}

\begin{solution}
De la même manière que pour $AC^0\subseteq NC^1$ on va simuler les
portes par des cascades de $\lor$ et $\land$. Quitte à rajouter des
portes $\top$ et $\bot$, on peut facilement supposer que les entrées
des portes MAJORITÉ sont d'arité des puissance de $2$.


Pour simuler MAJORITÉ($a_1, \dots, a_k$), on va compter le nombre de 1
dans $a_1, \dots, a_k$. L'idée c'est d'utiliser un half-adder. On va
récursivement calculer en profondeur constante des additions de trois
nombres $x$, $y$, $z$ qui vont produire deux nombres $c$ et $s$ tels
que $c+s=x+y+z$. Pour cela $c$ va contenir le reste ($carry$) et $s$
la somme donc $s_i=x_i+y_i+z_i$ et $c_i=(x_i\land y_i) \lor (z_i\land
y_i) \lor (x_i\land z_i)$.

Maintenant $half\_popcount(a_1, \dots, a_{2k})$ retourne deux vecteurs
de bits, le nombre de $\top$ et un reste.

Si $(s_1,c_1)=half\_popcount(a_1, \dots, a_k)$ et
$(s_2,c_2)=half\_popcount(a_{k+1}, \dots, a_{2k})$ on calcule $s',c'
=s_1+s_2+c_2$ et on renvoie le résultat de $s'+c_1+c'$.
\end{solution}

\begin{question}
  Montrer que le problème de parité est dans $TC^0$.
\end{question}

\begin{solution}
  Il suffit de tester pour chaque valeur de $k$ si le nombre de $1$ se
  trouve est $2k$ (et donc plus grand que $2k$ mais pas $2k+1$):

 $$parity(a_1, \dots, a_n) = \lor_{k\leq n/2} T_{2k}(a_1, \dots
  a_n)\land \lnot T_{2k+1}(a_1, \dots a_n) $$
\end{solution}

\begin{question}
  Montrer que le problème de la multiplication est dans $TC^0$.
\end{question}

\begin{solution}
  Pour simplifier la présentation de cette solution, nous allons
  procéder de façon modulaire.

  \paragraph{Passage de la multiplication de deux nombres à l'addition de $n$ nombres}
  On ramène facilement le problème de la multiplication de deux
  nombres de taille $n$ à l'addition de $n$ nombres de taille $2n$ car
  $(a\times b) = \sum_{1\leq j\leq n} \sum_{1\leq k\leq n} 2^{k+j}
  (a_j\land b_{k}) $.

  \paragraph{Passage de l'addition de $m$ nombres de tailles $n$
    à l'addition en parrallèle de $ln(m)$ nombres de taille $2ln(m)$.}
  
   Notons $a^1, \dots, a^m$ les nombres à additionner et $r^i = \sum_j
   a^j_i$. Comme $r^i$ est la somme de $m$ nombres valant $0$ ou $1$,
   $r^i\leq m$ et donc $r^i$ tient sur $ln(m)$ bits. On veut calculer
   le bit $r^i_j$ en profondeur constante.  Notons pour cela
   $bit(k,j)$ qui vaut $1$ si la représentation binaire de $k$
   contient un $1$ en $j$-ème position on a:

  $$r^i_j = \bigvee_{1\leq k \leq n\atop bit(k,j)=1} T_k(a^1_i, \dots, a^m_i)$$

On a par ailleurs que $\sum_k a^k = \sum_i 2^i r^i$ avec :
  \[
  \begin{matrix}
    a^1_1 & \cdots & a^1_n \\
    \vdots & \ddots & \vdots \\
    a^m_1 & \cdots & a^m_n \\[0.2cm] \hline
    r_1 = \sum_k a^k_1 & \cdots & r_n  = \sum_k a^k_n\\    
    
  \end{matrix}
  \]

Comme chacun des $r^i$ tient sur $ln(m)$ bits, on va regrouper les
$r^i$ en bloc de taille $B=ln(m)$ bits en calculant
$$v^\ell = \sum_{1\leq k \leq ln(m)} 2^k r^{k+\ell}$$ et donc on a
toujours :

$$ \sum_k a^k = \sum_i 2^i r^i = \sum_\ell v^\ell 2^{B\ell} $$

Nous allons montrer ensuite comment faire le calcul de $v^\ell$ en
profondeur constante et taille polynomiale. Montrons d'abord comment
s'en sortir si l'on sait calculer les $v^\ell$.


Une fois que les $v^\ell$ sont calculés on calcule $x = \sum_\ell
2^{3B\ell} v^{3\ell}$ et $y=\sum_\ell 2^{B(3\ell+1)} v^{3\ell+1}$ et
$z=\sum_\ell 2^{B(3\ell+2)} v^{2\ell +2}$. Chacun des $v^\ell$ tient
sur $2 ln(m)$ bits on a que les sommes plus hauts peuvent être
transformées en OU bit à bit car les représentations binaires de ces
nombres sont disjointes (entre $2^{B\ell} v^\ell$ et
$2^{B(\ell+3)}v^{\ell+3}$ il n'y a pas de bits en commun car $v^\ell\leq 2^{2B}$).


Enfin la dernière étape est de faire la somme $x+y+z$ mais cela peut
être fait en profondeur constante puisque la somme est dans
$AC^0\subseteq TC^0$.

\paragraph{Calcul des $v^\ell$ en profondeur constante}

Ce que l'on a envie de faire pour calculer $v^\ell$ c'est d'utiliser
sa table de vérité. Le problème c'est que chaque bit de $v^\ell$
dépend de $ln(m)\times ln(m)$ bits des $r^i$. Donc la table de vérité
peut être exponentielle en $ln(m)\times ln(m)$ ce qui est plus que
polynomial en $m$. 

Le calcul d'un $v^\ell$ correspond donc à faire la somme de $ln(m)$
nombres de taille $2ln(m)$. En itérant \emph{une seule fois} le
processus qui nous a permis de passer d'une somme de $a^k$ à une somme
de $v^\ell$, on se ramène à écrire $v^\ell = \sum 2^{B'j} w^k$. Où les
$w^k$ sont de taille logarithmique en la taille $v^\ell$ et donc
$|w^k|\leq 2 ln(ln(m)^2) \leq 4 ln(ln(m)) $

Maintenant les $w^k$ sont de taille très petite par rapport à $n$ et
donc le calcul de chaque $w^k$ peut se faire en profondeur constante
en utilisant sa table de vérité (comme à la question 2). Passer par la
table de vérité produit bien un circuit de profondeur constante mais
de taille exponentielle. Cependant cette taille est exponentielle en
le nombre de bits dont dépend $w^k$ qui ici est $4 ln(ln(m))\times
ln(ln(m))$ et donc sub-linéaire en $m$. Notez qu'il y a un nombre
polynomial de $w^k$ car il y a $ln(m)/ln(ln(m))$ par $v^\ell$ et qu'il
y a $m/ln(m)$ $v^\ell$ par $a^k$.

Une fois que les $w^k$ sont calculés on passe des $w^k$ aux $v^\ell$
comme nous sommes passés des $v^\ell$ aux $a^k$ en en sommant un tous
les trois, ce qui nous donne des nombres $x'$, $y'$ et $z'$ et l'on
fait la somme $x'+y'+z'$.

\end{solution}

\end{document}

