A Computational Task: Decision problems a decision problem: \Sigma^{*} \to \left\{\text{no}, \text{yes}\right\} we often associate the “yes” instances of this decision problem as a L \subseteq \Sigma^{*} language “Given boolean formula \varphi, accept IFF \varphi is SAT” Function problems Give me a particular case of:
\begin{equation} f(w) : \Sigma^{*} \to \Sigma^{*} \end{equation}
note that there is a unique answer. “Give a formula \varphi, output lex first satisfying assignments/number of satisfying assignments” Search problem Given some input w \in \Sigma^{*}, return me zero, one, or many possible answers “Given boolean formula \varphi, give a satisfying assignment if there is one, otherwise output \bot”