\documentclass{article}
\input{6045preamble}
\usepackage{fancyheadings}

\newcommand{\shuffle}{\,\vert\vert\,}

\begin{document}
\handout{19}{Prof. Ron Rivest}{}{}{Final Exam}

\Large

This test is three hours long.  You may use the assigned text
(Sipser's ``Introduction to the Theory of Computation'') and your
notes (including class handouts, problem solutions, etc.).  You may
not use other materials.

!!! Be sure to write your full name \textbf{here and} on each page !!!

\vspace{1in}

\normalsize

\newpage
\pagestyle{fancy}
\lhead[{\large Name:\hspace{2in}}]{\large{Name:\hspace{2in}}}
\cfoot[]{}


\begin{problem}
\textbf{Short-Answer Questions: (3 points each)}
\begin{enumerate}

\item 
  Suppose $L$ is a language and $M$ is a probabilistic
  polynomial-time decider such that
  \begin{itemize}
  \item $Pr\left[ M(x) \mbox{ accepts } \vert x \in L \right] 
         \leq \frac{1}{10}$,
    and 
   \item $Pr\left[ M(x) \mbox{ accepts } \vert x \not \in L \right] 
          \geq \frac{9}{10}$
  \end{itemize}
  Is $L \in \BPP$?
  (Explain briefly.)

\vspace{1in}

\item 
  Suppose the language $L$ is the union of the 
  sublanguages $L_1$, $L_2$, \ldots, where the number
  of such sublanguages may be finite or infinite, and where
  each language $L_i$ is known to be regular.
  How hard can it be to recognize $L$?  (What is the worst
  it could be, given these constraints?)

\vspace{1in}

\item   
  Due to manufacturing limitations, the Turing machines made by ACME Computer
  are limited to having a tape with at most $2^{n}$ tape squares when the
  input has size $n$.
  Is the Halting Problem for an ACME TM decidable?
  (Explain briefly.)

\vspace{1in}

\item
  It is true that if $P=NP$, then $PRIMES \in NP$.
  Can you explain (briefly) why?

\vspace{1in}

\item         
  True or false: it is impossible for a deterministic encryption scheme to
  be semantically secure.
  (Explain briefly.)

\vspace{1in}


\end{enumerate}
\end{problem}


%
% Regular Languages
%

\newpage

\begin{problem} \textbf{(15 points)}
  The operation of \emph{shuffle} is important in the study of
  concurrent systems. If $x$, $y \in \Sigma^*$, then $x \shuffle y$ is
  the set of all strings that can be made by shuffling $x$ and $y$
  together like a deck of cards. For example,
  $$ab \shuffle cd = \set{abcd, acbd, acdb, cabd, cadb, cdab}$$
%  The set $x \shuffle y$ can be defined inductively:
%  \begin{eqnarray*}
%    \epsilon \shuffle y & = & \set{y}\\
%    x \shuffle \epsilon & = & \set{x}\\
%    xa \shuffle ya &=& \set{(x \shuffle yb) \cdot a} \cup  \set{(xa \shuffle y) \cdot b}
%  \end{eqnarray*}
  The shuffle of two languages $A$ and $B$, denoted $A \shuffle B$, is
  the set of strings obtained by shuffling a string from $A$ with a
  string from $B$:
  $$A \shuffle B = \bigcup_{
    \begin{array}{c}
      x \in A\\
      y \in B
    \end{array}
    } x \shuffle y
  $$
  Prove that if $A$ and $B$ are regular, then $A \shuffle B$ is regular also.
  (Hint: can you design an FA that recognizes $A \shuffle B$?)
\end{problem}

% \newpage
% 
% \begin{problem} \textbf{(15 points)}
%   Let $\Sigma = \set{\mathtt{(,)}}$,
%   the alphabet containing just the left and right parentheses symbols.
%   Let \textit{BAL} be the
%   language of balanced sequences of parenthesis. For example,
%   ``\texttt{()((()())())}'' 
%   is in \textit{BAL} but
%   ``\texttt{)(()}'' 
%   is not. Prove that the language \textit{BAL} is not regular.
% \end{problem}
%

\newpage

%
% Decidability and recognizability
%

%
% In test given to class, class instructed to ignore it. 

%\begin{problem} \textbf{(15 points)}
%  A Turing Machine $M$ has an \emph{unreachable state} if there is a state $q$
%  in $M$ so that no input will ever make $M$ enter state $q$. Show
%  that the language
%  $$
%  US = \cset{\rep{M}}{M \mbox{ has an unreachable state }}
%  $$
%  is undecidable.
%\end{problem}

% \newpage

\begin{problem} \textbf{(15 points)}
  One of the following two sets is Turing-recognizable, and the other is
  not. Which one is which?  Prove your answer to be correct. 
  (Hint: can you prove that they can't both be recognizable?)
  \begin{itemize}
  \item $ A = \cset{\rep{M}}{M \mbox{ accepts at most 481 distinct inputs}}$
  \item $ B = \cset{\rep{M}}{M \mbox{ accepts more than 481 distinct inputs}}$
  \end{itemize}
\end{problem}

\newpage

%
% P and NP
%

\begin{problem} \textbf{(15 points)}
Consider the \textit{FEEDBACK VERTEX SET} problem: 
\begin{quotation}
  Given a \emph{directed} graph $G=(V,E)$ and a number $K \leq |V|$,
  is there a subset $F \subseteq V$ such that $|F| \leq K$ and $F$
  contains a vertex from every directed cycle in $G$?
\end{quotation}
Show that the \textit{FEEDBACK VERTEX SET} problem is
$\NP$-complete. (Hint: Consider \textit{VC}.)
\end{problem}

\newpage

\begin{problem} \textbf{(15 points)}
Show that if $\P = \NP$, then there exists a polynomial-time algorithm
that takes in an instance $\rep{G,K}$ of the \textit{FEEDBACK VERTEX SET}
problem (as defined in the previous problem of this final) and returns either
\begin{itemize}
\item A feedback vertex set of size at most $K$, if one exists, or
\item A special character $\perp$ otherwise.
\end{itemize}

\end{problem}

\newpage

%
% Randomness and Crypto
%

\begin{problem} \textbf{(15 points)}
Suppose $L \in \BPP$ and $M$ is a probabilistic polynomial-time
decider so that
  \begin{itemize}
  \item $Pr\left[ M(x) \mbox{ accepts } \vert x \in L \right] \geq \frac{9}{10}$,
    and 
   \item $Pr\left[ M(x) \mbox{ accepts } \vert x \not \in L \right] \leq \frac{1}{10}$
  \end{itemize}
(Here the probabilities, as usual, depend only on the internal coin flips
of the machine $M$.)

Suppose that on any input $x$, the machine $M$ never flips more than $\log
(1+\length{x})$ coins (i.e., never uses more than $\log
(1+\length{x})$ bits of randomness). Show that $L \in \P$.  
\end{problem}


\newpage


\begin{problem} \textbf{(15 points)}
Suppose we have a public-key algorithm, a triple of
polynomial-time algorithms $(G,E,D)$, such that
\begin{itemize}
\item 
  $G$ is a randomized key-generation algorithm that produces key
  pairs $(PK, SK)$ when given as input a ``security parameter'' $k$
  (in unary, as $1^k$, as is usual),
\item 
  $E$ is a randomized encryption algorithm that takes in a public
  key $PK$ and a message $M \in \bit^*$, and produces a ciphertext
  $C = E(PK,M)$ in $\bit^*$.
\item 
  $D$ is a decryption algorithm that takes in an alleged ciphertext
  $C$ in $\bit^*$ and a secret key $SK$ and
  produces either
  \begin{itemize}
  \item $M$, if $C$ was produced by $E(PK,M)$ 
        (for the $PK$ associated with $SK$), or
  \item A special output $\perp$ otherwise.
  \end{itemize}
\end{itemize}

We define a public-key algorithm $(G,E,D)$ to be ``simply secure''
(a simpler notion than ``semantically secure'') if
for all messages $M_0$, $M_1$ in $\bit^*$,
for all probabilistic polynomial-time adversaries $A$,  
for all sufficiently large security paramters $k$,
$$ \Pr{(PK, SK) \leftarrow G(1^k);
       b \leftarrow \bit;
       C \leftarrow E(PK,M_b);
       d \leftarrow A(PK,C): 
       d=b} 
   < \frac{1}{2} + \frac{1}{k}.
$$
\end{problem}
(Here $b \leftarrow \bit$ means that $b$ is chosen uniformly at
random from the set $\bit$.)

Suppose further that there was an adversary that was able 
at least two-thirds of the time
to decrypt a doubly-encrypted message bit (0 or 1).
That is, suppose there exists a
probabilistic polynomial-time adversary $A'$ such that
for all $k$,
$$ \Pr{(PK, SK) \leftarrow G(1^k); 
       b \leftarrow \bit;
       C_1 \leftarrow E(PK,b);
       C_2 \leftarrow E(PK,C_1);
       d \leftarrow A'(PK, C_2): 
       d=b} 
   \ge \frac{2}{3}
$$ 
Show that the encryption scheme $(G,E,D)$ is not simply
secure.  (Hint: if you had $A'$, how would you distinguish
$E(PK,0)$ from $E(PK,1)$?)


\end{document}




