\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSG714}{Theory of Computation}{Spring 2009}{24 February 2009}{11}

\begin{center}
\Large{\bf Problem of the Week -- 6}
\end{center}

{\noindent \bf Minimizing NFAs}

This problem is taken from Sipser's text.  Given a regular language
(as a DFA or a regular expression), we know that there is a
polynomial-time algorithm to compute the smallest DFA, i.e., with the
smallest number of states.  (In class we discussed how the
Myhill-Nerode Theorem gives the number of states in the smallest DFA;
one can compute such a DFA in polynomial time using a dynamic
programming algorithm.)  The minimization problem may be much harder
for NFAs, however, as we see below.

For a CNF $\phi$ with $m$ variables and $n$ clauses, give a
polynomial-time algorithm to construct an NFA with $O(nm)$ states that
accepts every nonsatisfying assignment, where each assignment is
represented as a Boolean string of length $m$.  Then, prove that the
problem of minimizing NFAs -- i.e., given an NFA, find an equivalent
NFA with the smallest number of states -- cannot be done in polynomial
time unless $\mbox{P} = \mbox{NP}$.
\end{document}
