# Concise definitions for different types of computational problems

It is very common to define a decision problem $$L$$ in the following way. Let $$f \colon \Sigma^{*} \to \{0,1\}$$. Then $$L = \{x \in \Sigma^* \mid f(x) = 1\}$$. Effectively, $$L$$ contains all instances $$x \in \Sigma^*$$ that have a "yes" answer.

Are there similar concise definitions for other kinds of computational problems, like function problems, search problems, and counting problems?

Since a function problem is a generalization of a decision problem, I suppose we might take something like $$f \colon \Sigma^* \to \Sigma^*$$ and let $$L = \{(x,f(x)) \mid f(x) \text{ exists}\}$$, but that feels kind of hand-wavy. Search problems are like function problems with multiple instance-solution pairs, so we could use almost the same definition, and then counting problems can just be defined as the cardinality of the search problem set.

## 1 Answer

A search problem is defined by a verifier $$V: \Sigma^* \times \Sigma^* \to \{0,1\}$$. Given $$x$$, the goal is to find $$y$$ such that $$V(x,y)=1$$.

A counting problem is similar, but given $$x$$, the goal is to output the number of $$y$$ such that $$V(x,y)=1$$. There is a clear definition on Wikipedia.

There is a similarly concise definition of a function problem in Wikipedia. Refer to Wikipedia for the definition.