
%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~21~~~Decidability and Tractability
                        \hfill Winter 2024} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}

%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:


\begin{document}
\problemset{7}{February 28}{\bf {March 6}}


Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the text (Sipser). The
full honor code guidelines and collaboration policy can be found in the course syllabus.

Please attempt all problems. Please select {\em one} among Problem 1
and Problem 3 to be graded completely (and {\bf indicate clearly} which one); the other one
will receive 1 point for a credible attempt. {\bf Please turn in your solutions via
  Gradescope, by 1pm on the due date.}

\begin{enumerate}

\item A function $f:\Sigma^* \rightarrow \Sigma^*$ is called {\em length preserving} if for all $x \in \Sigma^*$,
\[|f(x)| = |x|.\]
A length-preserving function $f$ is called a {\em permutation} if it is onto, and note that in this case the inverse $f^{-1}$ is a well-defined function. Informally, such an $f$ is {\em one-way} if it can be computed in polynomial time, but it is hard to invert.
Much of cryptography is based on the assumption that there exist {\em length-preserving, one-way permutations}; indeed the multiplication of two primes (whose inverse is factoring) can be expressed in this way.

Let $f:\Sigma^* \rightarrow \Sigma^*$ be a {\em length-preserving, one-way permutation}, and let $g:\Sigma^* \rightarrow \{0,1\}$ be a polynomial-time computable predicate. A typical scenario is this: you hold a secret $x$, and you reveal $y = f(x)$ (which is easy to compute). If an adversary can obtain $x$ from $y$, she is able to compute a bit $g(x)$ that she is not supposed to know. In this problem you will show that the adversary's task is in NP $\cap$ coNP; in other words, you should show that the following language is in NP $\cap$ coNP:
\[L = \left \{y : g(f^{-1}(y)) = 1\right \}.\]
A side comment: this shows that it is possible (if P $=$ NP $\cap$ coNP) for the adversary's task to become easy, and much of cryptography to become insecure, while it might still be the case that P $\neq$ NP.

\item In this problem we consider a model of distributed
computation. We have $n$ {\em processes}, modeled as directed
graphs $G_1 = (V_1, E_1), \ldots, G_n = (V_n, E_n)$. The nodes of
graph $G_i$ are the states of process $i$; it can potentially move
from state $v$ to state $w$ iff there is an edge $(v, w) \in E_i$.
Here is how we model the {\em distributed} nature of the
computation performed by these $n$ processes: we are given a list
of pairs of edges $P = ((e_1, e_1'), (e_2, e_2'), \ldots, (e_m,
e_m'))$ such that for each $i$, $e_i$ and $e_i'$ belong to the
edge sets of two different graphs from among $G_1, \ldots, G_n$.
These are intended to specify the possible communications between
processes: if process $i$ is in state $v \in V_i$ and process $j$
is in state $v' \in V_j$, then (with some communication), they can
move into state $w$ and $w'$ respectively iff the pair $((v, w),
(v', w'))$ is in the list $P$.

Thus the state of the overall system is specified by a vertex in
each of the $n$ graphs; i.e., it is an element of $V = V_1 \times
V_2 \times \cdots \times V_n$. The relation $T \subseteq V \times
V$ (which is determined by $G_1, \ldots, G_n$ and $P$) describes
all possible transitions from one overall state to another. $T$
consists of all pairs $((v_1, v_2, \ldots, v_n), (v_1', v_2',
\ldots, v_n'))$ for which there are two indices $i, j$ for which
$((v_i, v_i'), (v_j, v_j')) \in P$ and for every other index $k$,
$v_k = v_k'$. In other words, at each step, one of the
communications specified in list $P$ may occur, changing the state
of the associated two processes, while the other processes remain
unchanged.

A central problem in designing distributed systems is avoiding
{\em deadlock}. In this model, a {\em deadlock state} is a state
$v \in V$ for which there is no $w \in V$ with $(v, w) \in T$.

\begin{enumerate}
\item  It would be nice to be able to automatically examine a
system modelled in this way and determine if there is a deadlock
state. Unfortunately this is likely to be hard. Show that the
following language is NP-complete:

\begin{eqnarray*}
\mbox{{\sc deadlock}} &=& \{(G_1, G_2, \ldots, G_n, P)  :
\mbox{directed graphs $G_1, G_2, \ldots, G_n$ and the list $P$} \\
& & \mbox{specify a system with a deadlock state.}\}
\end{eqnarray*}

Hint: reduce from 3-SAT, producing one process for each clause.

\item In certain scenarios, it is difficult to design a system
with no deadlock state. Instead, we aim to design a system in
which a deadlock state is not {\em reachable} from an initial
state of the system. As before it would be nice to be able to
automatically verify this property. Unfortunately this is likely
to be even harder. Show that the following language is PSPACE-hard
(it is in fact PSPACE-complete, but in this problem you are not
required to show that it is in PSPACE):

\begin{eqnarray*}
\mbox{{\sc reachable deadlock}} & = & \{(G_1, G_2, \ldots, G_n, P,
v) :
\mbox{directed graphs $G_1, G_2, \ldots, G_n$} \\
& & \mbox{and the list $P$ specify a system with a deadlock state}
\\ & & \mbox{that is reachable from state $v \in V$}\}
\end{eqnarray*}

Hint: refer to a tableau, in which each cell is either an alphabet
symbol $x$, or a pair $(x, q)$ indicating that the machine is
reading this cell, which contains symbol $x$, while in state $q$.
The number of processes will be the width of the tableau.

\end{enumerate}

\item In class we defined what it meant for a {\em language} to be
decidable in space $t(n)$. To properly define what it means for a
{\em function} to be computable in space $t(n)$, we need to use
multitape Turing Machines. We treat tape 1 as a {\em read-only}
input tape, tape 3 as a {\em write-only} output tape, tape 2 as a
read/write work tape, and we only count the space used on tape 2.

Formally, a function $f:\Sigma^* \rightarrow \Sigma^*$ is
computable in space $t(n)$ if there exists a 3-tape Turing Machine
$M$ with the following property: for every $w \in \Sigma^*$, if
$M$ is started with $w$ written on tape 1, then $M$ halts with
$f(w)$ written on tape 3, while touching at most $t(|w|)$ cells on
tape 2, never writing to tape 1, and never reading from tape 3.

Notice that it is possible to perform non-trivial computations
while using sub-linear space. In fact, many important functions
can be computed using only $O(\log n)$ space.

When we are discussing function computable in polynomial time, we
often implicitly use the (simple) fact that if $f$ and $g$ are
computable in polynomial time, then their composition is
computable in polynomial time. The analogous fact for
space-bounded computation is not so obvious, but it is true
nonetheless. Suppose functions $f:\Sigma^* \rightarrow \Sigma^*$
and $g:\Sigma^* \rightarrow \Sigma^*$ are both computable in space
$O(\log n)$. Show that the function $h:\Sigma^* \rightarrow
\Sigma^*$ defined by $h(w) = f(g(w))$ is computable in $O(\log n)$
space.



\end{enumerate}

\end{document}
