1
$\begingroup$

I am a bit confused on what the difference between a "function problem" and a "search problem" is.

The specific problem I have been studying is known as End-Of-The-Line:

Given two functions, $P(x)$ and $N(x)$, a value $v$ is said to be balanced if $N(P(v)) = P(N(v)) = v \lor N(P(v)) \neq P(N(v)) \neq v$. Given that $0^N$ is not balanced, find another value that is not balanced.

How is this not a search problem? This problem is complete for the class $PPAD$ which is a class of function problems, but the problem is essentially asking us to search a graph for an unbalanced node.

From wikipedia:

In the mathematics of computational complexity theory, computability theory, and decision theory, a search problem is a type of computational problem represented by a binary relation. Intuitively, the problem consists in finding structure "y" in object "x".

In End-Of-The-Line, the "y" structure is an unbalanced node that isn't $0$, and $x$ is the whole graph.

Is there something I'm not getting?

$\endgroup$
1
  • $\begingroup$ You can find a formal definition of a search problem at en.wikipedia.org/wiki/Search_problem. Please edit your question to describe the relation $R$ you want to define and explain why you believe it meets the conditions of that definition. Your quote is not a formal definition; it is some informal English that is not a substitute for referring to the actual mathematical definition. $\endgroup$
    – D.W.
    Mar 1, 2023 at 9:40

1 Answer 1

2
$\begingroup$

$\mathrm{PPAD}$ is a class of search problems, not of function problems. The notion of search problem is more general than that of function problem, which in turn is more general than a decision problem.

For a decision problem, we get an input and we need to answer yes or no.

For a function problem, we get an input and we need to compute a uniquely specified output.

For a search problem, we get an input and we need to compute some valid output.

$\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.