# Difference between function and search problems?

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?

• 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.
– D.W.
Mar 1, 2023 at 9:40

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