Computational Task
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”