\documentclass{scrartcl}
\usepackage[margin=1in, left=0.7in, right=0.7in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[english]{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]{december, the 21th 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}{Definition}
\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{AC}

\begin{defi}
  A boolean circuit with $n$ bits of inputs is a Directed Acyclic Graph
(DAG) where the leaves are the $n$ nodes representing the input and
the output is the only node whose degree is nul and where each
internal node is either an $\land$ or a $\lor$ (both can have
unbounded fan-in) or a $\lnot$ (with fan-in one).

Given a word $w\in\{0,1\}^n$ and a circuit $C$ whose input size is
$n$, we can evaluate the circuit on $w$ by replacing the $i$-th leaf
with $\top$ when $w_i=1$ and $\bot$ when $w_i=0$.
\end{defi}

\begin{defi}
We say that a \emph{family of (boolean) circuits}
$(C_i)_{i\in\mathbb{N}}$ accepts a language $L$ when for each $n\in
\mathbb{N}$, $C_n$ has $n$ bits of input and accepts $\{ w\in L \mid
|w|=n \}$.
\end{defi}

\begin{defi}
We define the class $AC^i$ as the class of decision problem for which
there exists a family of boolean circuits $(C_i)_{i\in\mathbb{N}}$
whose size is polynomial in the input and whose depth is bounded
$O(log(n)^i)$, i.e.  there exists $k$ such that for all $n\in
\mathbb{N}$, the depth of $C_n$ is bounded by $log(n^i)\times k$. The
size of $C_n$ is bounded by $P(n)$ for some polynomial $P$.
\end{defi}

\begin{question}
  Justify why we are only interested in the circuits of polynomial
  size (and not exponential of unbounded) ?
\end{question}

\begin{question}
  The parity problem corresponds to the language $\{ w\in\{0,1\}^*
  \mid |w|_1 \mbox{ is even}\}$.  Show that the \emph{parity problem}
  is in $AC^1$.
\end{question}

\begin{question}
  Show that \emph{addition} is in $AC^0$. In order to do that exhibits
  a family of circuits of bounded depth accepting the words $w=abc$
  with $|a|=|b|=|c|$ and $a+b=c$ ($a$, $b$ et $c$ are binary number in
  e.g. little-endian).
\end{question}

\begin{question}
  Show that \emph{multiplication} is in $AC^1$. Multiplication is
  accepting $w=abc$ such that $a\times b = c$ and $2|a|=2|b|=|c|$
  where $a$,$b$ and $c$ are binary numbers.
\end{question}


\begin{question}
  Show that all regular languages over $\{0,1\}$ are in $AC^1$.
\end{question}

\section{NC}
\begin{defi}
  We note $NC^i$ the class of decision problems accepted by a family
  of boolean circuits $(C_n)_{n\in \mathbb{N}}$ where the arity of
  gates $\lor$ and $\land$ is bounded to two and where the size of
  circuits is polynomial and the depth is $O(ln(n)^i)$.
\end{defi}

\begin{question}
  Show that for all $i$ we have $NC^i\subseteq AC^i \subseteq
  NC^{i+1}$.
\end{question}

\begin{question}
  Show that $NC^0\neq AC^0$.
\end{question}

\subsection{TC}

\begin{defi}
The class $TC^0$ corresponds to the class of decision problems
accepted by circuits where the gates are $\lnot$ and threshold gates
$T_k(x_1, \dots, x_n)$ (for all $k$) with $T_k(x_1,\dots, x_n)=|\{ i
\mid x_i=\top\}|\ge k$
\end{defi}

\begin{question}
  Show that the gates $\land$, $\lor$ and $MAJORITY$ can be encoded
  with a constant depth using where $MAJORITY(x_1, \dots, x_n)=\top$
  when half of its inputs are $\top$.
\end{question}


\begin{question}
  Show that $TC^0$ is equal to the class of problems accepted by
  circuits where the gates are only $\lnot$, $\land$, $\lor$, $\lnot$
  and $MAJORITY$ (all with unbounded fan-ins).
\end{question}

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

\begin{question}
  Show that $parity \in TC^0$.
\end{question}
\begin{question}
Show that $multiplication\in TC^0$.
\end{question}

\end{document}

