\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{9}

% DEFINE THE DUE DATE
\def\due{April 26, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.045/18.400 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\begin{document}

\mytitle

\prob{1: Pancake Problem -- Counting Steps}

\noindent Algorithm:

\begin{verbatim}
i = n                                 % time:   steps:         
while i > 0                           %
  find pancake i                      % O(n)    0
  insert spatula under it and flip    % O(1)    2
  find pancake n - i (0 = griddle)    % O(n)    0
  insert spatula above it and flip    % O(1)    2
  i = i - 1                           % O(1)    0
\end{verbatim}

With $O(n)$ iterations and $O(n)$ cost per iteration, this
algorithm takes $O(n^2)$ time. With $O(n)$ iterations and 4 steps
per iteration, this algorithm takes $4n$ steps.

\mypage

\prob{2: Multiplication}

\noindent $Mult = \{ \langle n,m,product \rangle : n, m, product$ are
binary encoded and $product = n*m\}$. {\em Assume some sort of
separation between $n,m,product$ on input tape.}

\vspace*{.15in}
General algorithm for Turing Machine to follow (the details get long and
complicated):

\begin{itemize}
\item For each digit in $n$, bit-multiply by each digit in $m$ and write
the result on the second tape, ending by writing a separator.
\item Bit-add the results on the second tape, making sure to add them in
proper shifted form. 
\item Compare the result from addition to $product$ on the first tape,
rejecting if they are not the same, accepting if they are.
\end{itemize}

The first step requires $O(|n|\cdot |m|)$ time. The length of the
multiplications written on the second tape is $m(n + 1)$. The second
step, the bit-addition, requires $O(|n|\cdot |m|)$ time since to add
corresponding digits in the multiplication results, $O(|n|)$ digits must
be traversed twice for $O(|m|)$ iterations. Finally, the third step, the
comparison, takes $O(|product|) = O(|n| \cdot |m|)$ time. So, the
running time of this algorithm is $3O(|n|\cdot |m|) = O(|n|\cdot |m|)$.

\mypage

\prob{3: Quadratic Reducibility}

\subprob{a} Algorithm:

\begin{enumerate}
\item Given input $x$, compute $f(x)$.
\item Run algorithm $M$ on $f(x)$.
\item If $M$ accepts $f(x)$, then accept $x$. If $M$ rejects $f(x)$,
reject $x$.
\end{enumerate}

\subprob{b} Time analysis:

\begin{enumerate}
\item $f(x)$ is computed in $O(|x|^d)$ time.
\item Algorithm $M$ runs in $O(c^{|x|^2})$ time since $|f(x)| =
O(|x|^2)$.
\item O(1)
\end{enumerate}

Therefore, this algorithm runs in $O(|x|^d) + O(c^{|x|^2}) =
O(c^{|x|^2})$ time. 

\mypage

\prob{4: Closure Properties of $\cal P$}

\subprob{a} $L_1 \cup L_2 \in \cal P$

Given input $x$, decide if it is in $L_1$. If not, then decide if it is
in $L_2$. Since both $L_1$ and $L_2$ are in $\cal P$, $L_1 \cup L_2$ can
be decided in polynomial time.

\subprob{b} $L_1L_2 \in \cal P$

For all possible ways of splitting a string of length $n$ into two
strings, decide if first part is in $L_1$ and decide if second part is
in $L_2$. Since there is a polynomial number of splitting the input
string (``$n$ choose 2'' $= n(n-1)/2$), and since $L_1$ and $L_2$ can be
decided in polynomial time, $L_1L_2$ can be decided in polynomial time.

\subprob{c} $\overline{L_1} \in \cal P$

Decide if input string is in $L_1$. If it is, then reject. If it isn't,
then accept. Since $L_1$ can be decided in polynomial time,
$\overline{L_1}$ can also be decided in polynomial time.

\subprob{d} $L_1^* \in \cal P$

Find all substrings of input string with length $n$. This takes $O(n)$
time. Decide if each of the substrings is in $L_1$. This takes
$nO(T(n))$ time. Look for contiguous substrings that are in $L_1$. This
takes $O(n^2)$ time. Therefore, $L_1^*$ can be decided in polynomial
time.

\mypage

\prob{5: Special Cases of {\em NP-complete} Problem}

\subprob{a} The algorithm to decide $EQ_{fa}$ would involve either
comparing the regexps for $A$ and $B$ or comparing the actual DFAs
themselves, state by state. Thus, it can be seen that the running time
would polynomially depend on the size of $A$ and $B$ and would not take
more than polynomial time.

\subprob{b} The algorithm to find a clique would most likely examine the
vertices of $G$, looking for a complete subgraph with $2k$ vertices.
Since it is limited to cliques of size $k$, the algorithm would examine
``$|V|$ choose $2k$'' possible combinations of vertices, which is a
polynomial number of combinations. Thus, $CLIQUE_k$ could be decided in
polynomial time.

\subprob{c} The algorithm would consist of first coloring a node red and
coloring all of its neighbors blue. Then examining each of its
neighbors' neighbors, trying to color them red. If there is a conflict
(i.e. one of them is blue), then reject. For all of its uncolored
neighbors, repeat the process of trying to color the neighbors blue,
rejecting if conflict, etc. For graoh with $n$ nodes, this algorithm
will generally take less than $O(n)$ iterations with less than $O(n)$
cost per iteration. So, at worst, this algorithm takes $O(n^n)$ time,
which is still polynomial.  Thus $2COLOR$ can be decided in polynomial
time.

\end{document}
