0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.