\documentclass[12pt,ifthen]{article}
\usepackage{url}
\usepackage{amsmath, amssymb, amsthm, amstext, graphicx,tikz, url}

\newif{\ifshowsoln}
\showsolntrue

\begin{document}

\newcommand{\bits}[1]{{\{0,1\}^{#1}}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\C}{{\sf C}}
\newcommand{\into}{\rightarrow}
\newcommand{\cvg}{\downarrow}
%\newcommand{\implies}{\rightarrow}
\newcommand{\st}{\mathrel{:}}

\centerline{\bf HW 6 CMSC 452. Morally Due April 9}

\centerline{\bf THIS HW IS TWO PAGES LONG!!!!!!!!!}

\ifshowsoln
\centerline{\bf SOLUTIONS}
\fi


\begin{enumerate}

\item
(25 points)
Assume $L_1\in DTIME(T_1(n))$ and $L_2\in DTIME(T_2(n))$.
Show that $L_1 \cup L_2 \in DTIME(T_1(n)+T_2(n))$.
(You can write pseudo code and note how long the program runs.
We ignore multiplicative and additive constants.)


\item
(25 points)
Formally (using tuple notation) define a 2-dimensional Turing machine with a single halt state.
Its input will be an rectangle of symbols.
Also, briefly describe the transition function.

\item
(25 points)
Let $L\in DTIME(T(n))$. Find polynomials $p$ such that $L^* \in DTIME(p(n) T(n)))$.
Give an algorithm that achieves this (it can use the algorithm for $L\in DTIME(T(n))$
and should be in pseudocode).


\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
A formula is in {\it DNF-form} if it is of the form
$$D_1 \vee D_2 \vee \cdots \vee D_L$$
where each $D_i$ is a $\wedge$ of literals.
(DNF stands for Disjunctive Normal Form.)
We call the $d$'s DISJUNCTS.
\begin{enumerate}
\item
(10 points)
Show that the following problem is in P:
given a formula in DNF form, determine if it is satisfiable.
\item
(8 points)
Write the following CNF formula in DNF form:
$$\phi_3=(x_1 \vee y_1) \wedge (x_2 \vee y_2) \wedge (x_3 \vee y_3)$$
How many disjuncts are in your formula?
\item
(7 points)
Write the following CNF formula in DNF form (you can describe
how you would do it, but be clear).
$$\phi_n=(x_1 \vee y_1) \wedge (x_2 \vee y_2) \wedge \cdots \wedge (x_n \vee y_n)$$
How many disjuncts are in your formula?
\item
(0 points but think about, DO NOT hand anything in for this part)
Your answer to (c) should be a large function, NOT a polynomial.
This means that YOUR attempt to get this CNF formula into a DNF
formula causes a blowup in size. 
I will ask the class to vote for either
\begin{itemize}
\item
There is a poly-sized DNF formula for $\phi_n$ AND this is known.
\item
There is NO poly-sized DNF formula for $\phi_n$ AND this is known.
\item
Whether or not there is a poly-sized DNF formula for $\phi_n$ is UNKNOWN TO SCIENCE!
\end{itemize}
\end{enumerate}


\end{enumerate}

\end{document}