\documentclass{article}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\newcounter{probcnt}
\newenvironment{problem}{\stepcounter{probcnt}{\bf Problem \arabic{probcnt}}.}{}
\newcounter{pracprobcnt}
\newenvironment{pracproblem}{\stepcounter{pracprobcnt}{\bf Practice Problem \arabic{pracprobcnt}}.}{}
\setlength{\parskip}{.4cm}
\setlength{\baselineskip}{15pt}
\setlength{\parindent}{0cm}
\newcommand{\compl}[1] {\overline{#1}}
\newcommand{\meanl} {[\![}
\newcommand{\meanr} {]\!]}
\newcommand{\means}[1] {\meanl #1 \meanr}
\newcommand{\propsem}[2] {#1\means{#2}}
\newcommand{\logprf} {\vdash}
\newcommand{\logcnsq} {\models}
\newcommand{\polyred}[2] {#1\: \leq_{\mathrm{P}}\: #2}
\newcommand{\mred}[2] {#1\: \leq_m\: #2}
\newcommand{\rec} {\mbox{REC}}
\newcommand{\re} {\mbox{RE}}
\newcommand{\core} {\mbox{co-RE}}
\newcommand{\dtime}[1] {\mbox{DTIME}(#1)}
\newcommand{\ntime}[1] {\mbox{NTIME}(#1)}
\newcommand{\dspace}[1] {\mbox{DSPACE}(#1)}
\newcommand{\nspace}[1] {\mbox{NSPACE}(#1)}
\newcommand{\polytime} {\mbox{P}}
\newcommand{\nptime} {\mbox{NP}}
\newcommand{\conp} {\mbox{co-NP}}
\newcommand{\lgspc} {\mbox{L}}
\newcommand{\expt} {\mbox{EXP}}
\newcommand{\nlgspc} {\mbox{NL}}
\newcommand{\nexpt} {\mbox{NEXP}}
\newcommand{\pspc} {\mbox{PSPACE}}
\newcommand{\co}[1] {\mbox{co-}#1}
\author{}
\date{}
\begin{document}
\hrule
\begin{center}
{\LARGE \sc $\underline{\mbox{Homework 2}}$} \\
{\Large \sc CS 498 MV: Logic in Computer Science}\\
\ \\
\begin{tabular}{ll}
Assigned: September 21, 2018 & Due on: October 2, 2018
\end{tabular}
\end{center}
\hrule
{\bf Instructions:} Please do not turn in solutions to the practice
problems. Solutions to the homework problems should be turned in as a
PDF file on Gradescope. See instructions on Piazza.
{\bf Recommended Reading:} Lectures 4 through 6: decidability,
recursive enumerability, and complexity theory.
$\underline{\mbox{\bf Practice Problems}}$
\begin{pracproblem}
Prove the following properties about polynomial time reductions.
\begin{enumerate}
\item If $\polyred{A}{B}$ then $\polyred{\compl{A}}{\compl{B}}$.
\item If $\polyred{A}{B}$ and $\polyred{B}{C}$ then $\polyred{A}{C}$.
\end{enumerate}
\end{pracproblem}
\begin{pracproblem}
Reductions allow one to compare the difficulty of two problems. But
the notion of reduction needs to be tuned according to what one's
goals are. This is illustrated in the following problem.
Consider the language $A = \{0\}$. Prove the following properties.
\begin{enumerate}
\item Let $B$ be any decidable language. Then $\mred{B}{A}$.
\item Let $B \in \polytime$. Then $\polyred{B}{A}$.
\end{enumerate}
This problem illustrates the deficiencies of different notions of
reductions. Many-one reductions are too coarse to enable one to
compare problems that are all decidable; this is evidenced by the fact
that one can show the simple language $A$ is ``at least as hard'' as
every decidable language (with respect to many-one
reductions). Similarly, polynomial time reduction are too coarse to
compare problems that are in $\polytime$.
\end{pracproblem}
\begin{pracproblem}
[Closure Properties] Consider languages $A,B \subseteq \Sigma^*$.
\begin{enumerate}
\item Prove that if $A,B \in \polytime$ then $A \cup B$, $A \cap B$, $AB$ and
$\compl{A}$ are in $\polytime$.
\item Prove that if $A,B \in \nptime$ then $A \cup B$, $A \cap B$, $AB$,
and $A^*$ are all in $\nptime$.
\end{enumerate}
\end{pracproblem}
\begin{pracproblem}
Let $H = \{\langle i,x \rangle\: |\: M_i \mbox{ halts on } x\}$, where
$M_i$ is the Turing machine whose code is $i$. Prove that $H$ is
$\nptime$-hard. Is $H$ $\nptime$-complete?
\end{pracproblem}
\newpage
$\underline{\mbox{\bf Homework Problems}}$
\begin{problem}
Determine whether or not each of the following problems about Turing
machines is decidable. Argue that your answer is correct. If your
answer is ``decidable'', then describe an algorithm (that always
halts) for the problem (at a suitably high level). If your answer is
``undecidable'', then prove your answer by constructing an
appropriate reduction.
\begin{enumerate}
\item Given a TM $M$ and input $x$, does $M$ run for more than
$2^{|x|}$ steps?
\item Given a TM $M$, is there an input $x$ such that $M$ runs for
more than $2^{|x|}$ steps on $x$?
\item Given a TM $M$, is there an input $x$ such that $M$ runs for
more than $2^n$ steps on $x$, where $n$ is the number of
states of $M$?
\item A computation is said to be nonerasing if, once a cell contains a
nonblank character, it is never changed afterwards. Given a $2$-tape
TM $M$, and an input word $x$ written on tape $1$. Is the
computation of $M$ on $x$ nonerasing?
\end{enumerate}
\end{problem}
\begin{problem}
Prove that the following problem, called $\mbox{MATCH}$ is
$\nptime$-complete. Given a finite set $S$ of strings of length $n$
over the alphabet $\{0,1,*\}$ determine if there exists a string $w$
of length $n$ over the alphabet $\{0,1\}$ such that for every string
$s \in S$, $s$ and $w$ have the same symbol in at least one
position. For example, if $S = \{001*,*100,10*0,1010\}$ then $w =
0000$ is a solution. However, if $S = \{00,*1,1*\}$ then there is no
string $w$ that ``matches''.
\end{problem}
\begin{problem}
Prove that if $\dspace{n} \subseteq \polytime$ then $\polytime =
\pspc$. \emph{Hint:} Let $L \subseteq \{0,1\}^*$ be recognized by
Turing machine $M$ in space $n^k$. Define $L_{{\rm pad}} =
\{x{\$}^{|x|^k-|x|}\: |\: x \in L\}$. What can you say about space
needed to solve $L_{{\rm pad}}$?
\end{problem}
\end{document}