---
title: "Computational Task"
source: https://www.jemoka.com/posts/kbhcomputational_task/
---

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