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

\newcommand{\halfnfa}{\mbox{{\sc Half-Paths-NFA}}}

\head{CSG714}{Theory of Computation}{Spring 2008}{20 February 2008}{11}

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

{\noindent {\bf Extracting solutions from decision algorithms}}

In our development of complexity theory, we have focused on decision
problems, where we only seek answers to ``yes/no'' questions.  More
often, we are interested in finding the actual solution that leads to
a ``yes'' answer.  In this problem, we consider extracting solutions
from decision algorithms.
\begin{itemize}
\item
Given a polynomial-time algorithm for deciding whether a Boolean
formula is satisfiable, describe a polynomial-time algorithm that,
given a Boolean formula $\phi$, actually produces a satisfying
assignment for $\phi$ if $\phi$ is satisfiable.
\item
Given a polynomial-time algorithm for deciding whether a directed
graph has a Hamiltonian path, describe a polynomial-time algorithm
that, given a directed graph $G$, actually produces a Hamiltonian path
of $G$ if it exists.
\end{itemize}

\end{document}