\documentclass[12pt]{article}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{fullpage}
\usepackage[left=1.0in,top=1.0in,right=1.0in,bottom=1.25in]{geometry}
\usepackage{bbold}
\usepackage{parskip}
\usepackage{tikz}
\usetikzlibrary{topaths,calc,automata,positioning}
\pagenumbering{gobble}


\setlength{\arraycolsep}{4pt}

\begin{document}
\begin{center}
\section*{CS 360 --- Introduction to the Theory of Computing \\ Assignment 5}
\subsection*{University of Waterloo, Spring 2018}
\end{center}
{\it Due 5:00 PM, July 25, 2018.}

\begin{enumerate}
\item 
A \emph{useless state} is a state that is never entered on any input string. Show that the language
\begin{equation*}
L = \{\langle M \rangle \mid \text{$M$ is a Turing machine and has a useless state} \}
\end {equation*}
is undecidable.

\item 
Show that the reduction relation $\leq$ is transitive.

\item 
Show that if $\mathbf P = \mathbf{NP}$, then every language $A \in \mathbf P \setminus \{\emptyset, \Sigma^*\}$ is $\mathbf{NP}$-complete.

\item 
Recall that the edit distance $d(x,y)$ of two words $x$ and $y$ is the fewest number of insertions, deletions, and substitutions required to transform $x$ into $y$. We can extend this definition to the edit distance between two languages $L_1$ and $L_2$ by
\begin{equation*}
d(L_1,L_2) = \min\{d(x,y) \mid x \in L_1, y \in L_2\}.
\end{equation*}
In other words, the distance between two languages is the distance between their two closest words. 

Show that if $L_1$ and $L_2$ are context-free languages, then $d(L_1,L_2)$ is uncomputable.

\item 
Let the class $\mathbf{coNP}$ be defined by
\begin{equation*}
\mathbf{coNP} = \{L \mid \overline L \in \mathbf{NP}\}.
\end{equation*}
That is, $\mathbf{coNP}$ is the class of languages that are complements of languages in $\mathbf{NP}$. As with many problems in computational complexity, it is not known whether $\mathbf{NP} = \mathbf{coNP}$.

Show that $\mathbf{NP} = \mathbf{coNP}$ if and only if there exists a language $L$ such that $L \in \mathbf{coNP}$ and $L$ is $\mathbf{NP}$-complete.

\end{enumerate}
\end{document}
