[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhcomputational_task.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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 “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\)”