\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amstex}

\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\newtheorem{theorem}{Teorema}
\newtheorem{exercise}{Ejercicio}
\newtheorem{corollary}{Corolario}
\newtheorem{lemma}{Lema}
\newtheorem{observation}{Observaci\'on}
\newtheorem{comentary}{Comentario}
\newtheorem{proposition}{Proposici\'on}
\newtheorem{definition}{Definici\'on}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}
\newcommand{\startproof}{\noindent{\em Dem:}\hspace{1em}}
\newenvironment{dem}{\startproof}{\qed}
\newenvironment{proof}{{\bf Dem:}\hspace{1em}}{\qed\newline}


\newcommand{\catedra}[4]{
   \pagestyle{headings}
   \thispagestyle{plain}
   \newpage
   \noindent
   \begin{center}
   \makebox[0in]{\framebox{
      \vbox{
    \hbox to 6in { {\bf MA-53G Intr. a la Criptograf\'{\i}a
                        \hfill Semestre Primavera, 1996}  }
       \vspace{4mm}
       \hbox to 6in { {\Large \hfill C\'atedra No. #1 : #2 \hfill} }
       \vspace{2mm}
       \hbox to 6in { {\it Transcriptor: #3 \hfill} }
      }
   }}
   \end{center}
   \markboth{C\'atedra No. #1 : #2}{C\'atedra No. #1 : #2}
   \vspace*{4mm}
}

% LISTA DE MACROS PERSONALES COMIENZA AQUI

\renewcommand{\emph}[1]{{\em #1}}
\newcommand{\plain}{{\cal P}}
\newcommand{\cipher}{{\cal C}}
\newcommand{\key}{{\cal K}}
\newcommand{\encrip}{{\cal E}}
\newcommand{\decrip}{{\cal D}}

\newcommand{\modulo}{{\cal Z}}
\newcommand{\kernel}{\mbox{\rm Ker}}
\newcommand{\determ}[1]{\mbox{\rm det}(#1)}
\newcommand{\mcd}[2]{\mbox{\rm mcd}(#1,#2)}
\newcommand{\mcm}[2]{\mbox{\rm mcm}(#1,#2)}
\newcommand{\set}[2]{\{#1\,|\,#2\}}
\newcommand{\smidge}{{\kern .05em}}  
\newcommand{\Colon}{{\smidge\colon\;\:}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}

\newcommand{\chapref}[1]{\mbox{Capitulo~\ref{#1}}}
\newcommand{\secref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\ssecref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Ap\'endice~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Teorema~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definici\'on~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corolario~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lema~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposici\'on~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figura~\ref{#1}}}
\newcommand{\tablref}[1]{\mbox{Tabla~\ref{#1}}}
% \newcommand{\eqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\ineqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\comref}[1]{\mbox{Comentario~\ref{#1}}}
\newtheorem{example}{Ejemplo}
\newcommand{\maximo}[2]{max\{#1,#2\}}
\newcommand{\Le}{${\cal L}$}
\newcommand{\Pol}{${\cal P}$}
\newcommand{\NP}{${\cal NP}$}
\newcommand{\coNP}{${\cal coNP}$}
\newcommand{\BPP}{${\cal BPP}$}
\newcommand{\RP}{${\cal RP}$}
\newcommand{\coRP}{${\cal coRP}$}
\newcommand{\ZPP}{${\cal ZPP}$}

% FIN LISTA DE MACROS PERSONALES

\begin{document}

% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
% (modificar los parametros en invocacion de la siguiente macro:
%  primer parametro: No. de catedra transcrita
%  segundo parametro: fecha de catedra transcrita
%  tercer parametro: Nombre del transcriptor
\catedra{15}{15 de Octubre}{Alejandro Hevia}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Clases de Lenguajes}

Nos abocaremos ahora a la tarea de definir m\'as formalmente ciertos
conceptos sobre los cuales descansa la criptograf\'{\i}a moderna.
Por ello, algunos conceptos b\'asicos de complejidad 
como lenguajes y m\'aquinas 
de Turing (determin\'{\i}sticas, no-determin\'{\i}sticas, probabil\'{\i}sticas)
se supondr\'an conocidos.\footnote{Para un tratamiento m\'as profundo, el
lector interesado puede consultar
el texto {\em Computational Complexity}, {\em C. Papadimitriou}, Addison
Wesley, 1994.}

\begin{definition}
  {\bf Lenguaje}
  Sea $\Sigma$ un conjunto finito de s\'{\i}mbolos. Diremos que 
$\Sigma$ es un alfabeto (finito). Sea $\Sigma^{*}$ el conjunto de
todos las posibles palabras sobre el alfabeto $\Sigma$. Un 
{\bf \em{lenguaje} \Le} es un conjunto de palabras sobre un alfabeto
finito $\Sigma$, tal que \Le $ \subseteq \Sigma^{*}$.
\end{definition}

\begin{definition}
  {\bf M\'aquina de Turing (Determinista)}
Definiremos informalmente una M\'aquina de Turing ($MT$) como 
consistente de un {\em control finito de estado} (llamado usualmente
{\em cabeza}), una {\em cinta de entrada } y una
{\em cinta de salida}. Ambas cintas, la de {\em entrada} como la de
{\em trabajo} consisten de celdas que pueden almacenar un s\'olo
s\'{\i}mbolo o letra de un alfabeto finito $\Sigma$. La cinta de 
trabajo tiene una cantidad infinita de celdas que pueden ser
usadas por la $MT$. El control finito tiene dos {\em cabezales}, 
cada uno apuntando a una celda espec\'{\i}fica en cada cinta, y
con la habilidad de moverse cada una hacia la izquierda o derecha.
Los estados posibles del {\em control finito} pueden ser cualquiera
de un conjunto finito $Q$ de estados, uno de los cuales se distinguir\'a 
como {\em estado de aceptaci\'on} y otro como {\em estado inicial}.
Asociado al {\em control finito de estados} tendremos una funci\'on
de transici\'on 
$\delta$ la cual, en base a las celdas actualmente apuntadas por 
los {\em cabezales} y el estado actual de la \em{cabeza}, describe
d\'onde mover los cabezales (izquierda o derecha) y el nuevo
estado al cual entra la {\em cabeza}. Esta funci\'on puede tambi\'en
especificar un cambio en la celda actualmente apuntada por el
cabezal de la cinta de trabajo (no as\'{\i} en la cinta de {\em
entrada}).\\
La entrada de una $MT$ consiste de una {\em palabra} (una
concatenaci\'on finita de letras del alfaveto $\Sigma$). Esta
palabra es colocada entre un s\'{\i}mbolo especial de $\Sigma$,
\$, al comienzo de la {\em cinta de entrada}, un s\'{\i}mbolo
en cada celda. Inicialmente, cada celda de la cinta de trabajo 
posee el s\'{\i}mbolo {\em blanco} y los {\em cabezales} 
apuntan a la primera celda de la cinta de entrada y a la
primera celda de la cinta de trabajo.
\end{definition}

%\begin{definition}
%  {\bf M\'aquina de Turing No Determinista}
%\end{definition}

\begin{definition}
  {\bf M\'aquina de Turing Probabilista}
Una m\'aquina de Turing probabilista $M$, es una $MT$ que posee
un estado especial de {\em petici\'on de lanzamiento de moneda}.
Cuando $M$ entra en este estado, adquiere conocimiento sobre
el resultado del lanzamiento de una moneda, el cual puede
ser ``cara" ($1$) o ``sello" ($0$) (cada uno con probabilidad
$\frac{1}{2}$). Cada lanzamiento de moneda se considera que 
ocurre en forma independiente de cualquier otro lanzamiento. 
\end{definition}

\begin{definition}
  {\bf Aceptaci\'on de Palabras}\\
  Diremos que una m\'aquina de Turing $M$ {\em acepta} una palabra
  $x$ de un lenguaje \Le  si la m\'aquina $M$ al recibir en su cinta 
  de entrada la codificaci\'on \footnote{No 
  entraremos aqu\'{\i} en el detalle de c\'omo debe hacerse esta 
  codificaci\'on y consideraremos la noci\'on intuitiva de
  este proceso, bajo el supuesto que este 
  s\'olo realiza lo ``justo y necesario''.} 
  de la palabra $x$, eventualmente 
  se detiene quedando en su cinta de trabajo la codificaci\'on
  de la palabra {\em aceptar}.\footnote{Basta que sea alguna codificaci\'on 
  predefinida de ella.} Esto \'ultimo lo notaremos por
  $M(\,x\,)=\,acepta$.\\
\end{definition}

\begin{definition}
  {\bf Aceptaci\'on de Lenguajes}\\
  Diremos que una m\'aquina de Turing $M$ {\em acepta} un lenguaje \Le
  si ocurre que:
  $M$ acepta $x$  si y s\'olo si $x \in $ \Le.
\end{definition}

\begin{definition}
Decimos que un lenguaje \Le est\'a en \Pol si
existe una m\'aquina de Turing $M$ y un polinomio $p$ tal que

\begin{enumerate}
  \item $x \in L $ si y s\'olo si $M$ acepta $x$, es decir $M(x)=\,acepta$.
  \item Al operar $M$ en la entrada $x$ realiza a lo m\'as 
  $p (\,|\,x\,|\,)$ pasos, donde $|\,x\,|$ es el n\'umero de
  caracteres de $x$.
\end {enumerate}
\end{definition}

La clase de lenguajes \Pol es considerada cl\'asicamente como la
clase de los lenguajes ``eficientemente computables". 

\begin{observation}
  Notar que \Pol es cerrado bajo complemento, pues pertenencia en el
  lenguaje $\overline{{\cal L}}$ puede ser decidida en tiempo polinomial
  por la m\'aquina de Turnig $M^{\prime}$ tal que $M^{\prime} (x)
  \,=\, acepta$ si y s\'olo si $M (x) \,\neq\, acepta$.
\end{observation}

\begin{definition}
  Decimos que un lenguaje \Le pertenece a \NP si existe 
  una m\'aquina de Turing
  $M\,(\,\cdot\,,\,\cdot\,)$ y polinomios $p$ y $q$ tales que 

  \begin{enumerate}
    \item Si $x \in $ \Le entonces $\exists \,y, \,|y| \leq q(|x|)$
      tal que $M(x,y)=\,acepta$.
    \item Si $x \not \in $ \Le entonces $\forall \,y, \,|y| \leq 
            q(|x|)$ tal que $M(x,y)\neq\,acepta$.
    \item $M$ en la entrada $x$ se detiene en a lo m\'as 
      $p(\,|x|\,)$ pasos.
  \end {enumerate}

\end{definition}

Notar que esta definici\'on es equivalente a la definici\'on 
de \Le $ \in $ \NP si existe una m\'aquina de Turing no-determinista de tiempo
polinomial $M$, la cual acepta $x$ si y s\'olo si $x \in $ \Le. Aqu\'{\i}, 
la palabra
$y$ de la definici\'on corresponde a la {\em adivinanza} de la m\'aquina
de Turing no-determinista.

\begin{observation}
  Si \NP es cerrado o no es un problema abierto. Su complemento 
  se denomina \coNP.
\end{observation}

\begin{definition}
  Decimos que un lenguaje \Le est\'a en \BPP si 
  existe una m\'aquina de Turing $M\,(\,\cdot\,,\,\cdot\,)$ y 
  polinomios $p$ y $q$ tales que
  \begin{enumerate}
      \item Si $x \in $ \Le entonces $ 
        \Bbb{P}_{\rho \in \{0,1\}^{q(|x|)}}
        [\,M(x,\rho)=\,acepta]\, \ge
        \frac{2}{3} $
      \item Si $x \not \in $ \Le entonces $ 
        \Bbb{P}_{\rho \in \{0,1\}^{q(|x|)}}
        [\,M(x,\rho)=\,acepta]\, \leq
        \frac{1}{3} $
      \item Al operar $M$ sobre la entrada $x$
               realiza a lo m\'as $p(|x|)$ pasos.
  \end {enumerate}
\end{definition}

\begin{exercise}
Demuestre que en la definici\'on de \BPP
es posible reemplazar 
las constantes $\frac{2}{3}$ y $\frac{1}{3}$ por $1-\epsilon$ 
y $\epsilon$ respectivamente
(con $\,0 \,< \,\epsilon \,<\, \frac{1}{2}\,$)
y la clase \BPP no se modifica.
\end{exercise}

\begin{proof}
Denotemos por $\BPP_{\epsilon}$ al conjunto definido en forma an\'aloga 
a \BPP, cambiando las constantes $\frac{2}{3}$ y $\frac{1}{3}$ por
$1-\epsilon$ y $\epsilon$ respectivamente. \\
Supongamos que \Le $\in $ \BPP$_{\epsilon}$ y probemos que 
\Le $ \in $\BPP$_{\delta}$ donde \\
$0 < \delta < \epsilon < \frac{1}{2}$.\\
Con ello, se sigue que existe una m\'aquina de Turing $M$, tal que
si $x \in $ \Le

  \begin{equation*}
  \Bbb{P}_{\rho \in \{0,1\}^{q(|x|)}}
  [\,M(x,\rho)=\,acepta]\, \leq 1-\epsilon \,.
  \end{equation*}
Luego, si $x \not \in $ \Le sigue que
  \begin{equation*}
  \Bbb{P}_{\rho \in \{0,1\}^{q(|x|)}}
  [\,M(x,\rho)=\,acepta]\, \leq \epsilon \,.
  \end{equation*}

Sea $M^{\prime}$ otra m\'aquina de Turing que simula $k$ veces la 
m\'aquina $M$ y acepta si y s\'olo si al menos $\frac{k}{2}$ de 
estas simulaciones llevan a $M$ a aceptar. Sea $\chi$ el 
n\'umero de veces que $M$ acepta.\\

Si $x \in L$, entonces como ${\chi \sim Bin(k,1-\epsilon)}$
tendremos que
  \begin{equation*}
   \begin{split}
      \Bbb{P}[\,M^{\prime}\,\text{acepta}\,] 
   &= \Bbb{P} [\chi \ge \frac{k}{2}]\\
   &= 1-\Bbb{P} [\chi < \frac{k}{2}]\\
         &= 1-\Bbb{P} [\Bbb{E}(\chi) -\chi > k\,(\frac{1}{2}-\epsilon)]\\
         &\ge 1-\Bbb{P} [|\chi - \Bbb{E}(\chi)| > k\,(\frac{1}{2}-\epsilon)]\\
         &\ge 1-\frac{\Bbb{V}ar \chi}{k^2(\frac{1}{2}-\epsilon)^2} \\
         &= 1-\frac{1}{k} \frac{\epsilon (1-\epsilon)}{(\frac{1}{2}-\epsilon)^2}\\
   &= 1-\delta\\
   \end{split}
  \end{equation*}
(donde denotamos por $\delta$ a $\frac{1}{k} 
\frac{\epsilon (1-\epsilon)}{(\frac{1}{2}-\epsilon)^2}$).\\
  Si $\epsilon$ es constante, esta probabilidad puede hacerse 
arbitrariamente cercana a 1 al aumentar $k$. 

An\'alogamente, si $x \not \in $ \Le, entonces como ${\chi \sim Bin(k,\epsilon)}$
tendremos que
  \begin{equation*}
   \begin{split}
      \Bbb{P}[\,M^{\prime}\,\text{acepta}\,] 
   &\le \Bbb{P} [\chi \ge \frac{k}{2}]\\
         &= \Bbb{P} [\chi - \Bbb{E}(\chi) \ge k\,(\frac{1}{2}-\epsilon)]\\
         &\le \Bbb{P} [|\chi - \Bbb{E}(\chi)| \ge k\,(\frac{1}{2}-\epsilon)]\\
         &\le \frac{\Bbb{V}ar \chi}{k^2(\frac{1}{2}-\epsilon)^2} \\
         &= \frac{1}{k} \frac{\epsilon (1-\epsilon)}{(\frac{1}{2}-\epsilon)^2}\\
         &= \delta
   \end{split}
  \end{equation*}

Luego se tiene que la m\'aquina de Turing $M^{\prime}$ acepta cuando
$x \in $ \Le con probabilidad al menos $1-\delta$ tal que $0< \delta < \epsilon < 
\frac{1}{2}$ y con probabilidad $\delta$ cuando $x \not \in $ \Le. Luego
$L \in \BPP_{\delta}$.

Queda al lector propuesto demostrar que se tiene el resultado
incluso para $\epsilon = \frac{1}{2}-\frac{1}{p(n)}$ donde $p$ es un polinomio 
cualquiera y $n = \,|x|$.
\end{proof}

\begin{definition}
  Decimos que un lenguaje \Le est\'a en \RP si 
  existe una m\'aquina de Turing $M\,(\,\cdot\,,\,\cdot\,)$ y 
  polinomios $p$ y $q$ tales que
  \begin{enumerate}
      \item Si $x \in $ \Le entonces $ 
        \Bbb{P}_{\rho \in \{0,1\}^{q(|x|)}}
        [\,M(x,\rho)=\,acepta]\, \ge
        \frac{2}{3} $
      \item Si $x \not \in L$ entonces $ 
        \Bbb{P}_{\rho \in \{0,1\}^{q(|x|)}}
        [\,M(x,\rho)=\,acepta]\, =\, 0 $
      \item Al operar $M$ sobre la entrada $x$
               realiza a lo m\'as $p(|\,x\,|)$ pasos.
  \end {enumerate}
\end{definition}

\begin{exercise}
Demuestre que en la definici\'on de {\cal RP} es irrelevante 
el valor $\frac{2}{3}$ de la cota para
la probabilidad de aceptar en el caso $x \in L$
y puede ser reemplazada por cualquier constante $\epsilon \in
(\,0\,,\,1\,)$. 
\end{exercise}

\begin{observation}
  La definici\'on de \coRP es an\'aloga s\'olo que 
  exige que la probabilidad de aceptar cuando $x \in $ \Le 
  sea igual a
  $1$ y la probabilidad de aceptar cuando $x \not \in $ \Le
  sea menor o igual a $\frac{1}{3}$.
\end{observation}

\begin{definition}
  Decimos que un lenguaje \Le est\'a en \ZPP si 
  existe una m\'aquina de Turing probabil\'{\i}stica $M\,(\,\cdot\,)$ y 
  un polinomio $p$ tal que
  \begin{enumerate}
      \item $x \in L$ si y s\'olo si $M(\,x\,)=\, acepta$.  
      \item La esperanza del n\'umero de pasos que $M$
        ejecuta en la entrada $x$ es a lo m\'as 
        $p(\,|x|\,)$.
  \end {enumerate}
\end{definition}

{\large \bf Relaciones entre lenguajes}

Se sabe que \Pol $ \subseteq $ \NP , que \Pol $ \subseteq $
\RP $ \subseteq $ \BPP . Adem\'as se cumple que
\ZPP= \RP \,$ \cap $ \, \coRP , que \coRP
\,$ \subseteq $ \,\BPP  y que \RP \, $ \subseteq $ \, \NP  
(basta adivinar el resultado del ``lanzamiento de monedas" que 
realiza la m\'aquina de Turing probabil\'{\i}sta).\\
Actualmente no se sabe si es cierto que \NP $ \ne $ \Pol 
aunque se conjetura que  
es cierto. Asimismo, a\'un no se
clarifica cu\'al es la relaci\'on entre \BPP y \NP o entre 
\BPP y \Pol.
\footnote{Un ejemplo de lenguaje que est\'a es \BPP y no
se sabe a\'un si est\'a en \Pol es el lenguaje de todos los enteros
primos (esto es, verificar primalidad).}

\end{document}
-------> cortar aqui <------------


