# Encoding of continuous functions in PPAD

I'm studying the complexity class PPAD (from the seminal 1994 work by Papadimitriou) which contains complete problems such as computing Nash equilibria or finding the fixed point of a Brouwer map. Specifically, I have two questions regarding the motivation of the computational Brouwer problem, and the representation of a continuous function $$F: K \rightarrow K$$ as an input to a Turing machine, where $$K$$ is a closed convex domain.

1. The Brouwer problem seems to be challenging to define since the problem would require as input a Lipschitz function $$F$$, which can not in general be encoded. It seems from the 1994 paper that this issue is cleverly side-stepped when defining the Brouwer problem by assuming the directionality of the vector $$x - F(x)$$ is computed as a coloring by a given Boolean circuit, and I understand that this reduces to an approximate fixed point via Sperner's lemma. However, could it be the case that computing a fixed point of a Lipschitz continuous function in general is strictly harder than PPAD-complete problems, since continuous functions where such a succinct Boolean circuit exists is a subset of all Lipschitz continuous functions on $$K$$?

2. Related to the above, are there restricted classes of Lipschitz functions that can be easily represented such that finding a fixed point is still PPAD-complete? For instance, functions that are compositions and arithmetic combinations of simple functions such as $$\sin x, \max(x, y),\ldots$$, or continuous functions that can be represented succinctly as a computational graph, or a L-layer W-width ReLU neural network, etc.

• How do you input a continuous function $F$? Depending on the input method, computing $F(x)$ even approximately can be a hard problem. Instead of going into details about this, a natural assumption is that the direction of $x-F(x)$ can be computed, without going into details. Using such oracles are common in computations, see for example en.wikipedia.org/wiki/Matroid_oracle. Commented Sep 12, 2023 at 13:34
• @domotorp how about if we restrict our attention to easily computable continuous functions: Can the problem of finding fixed points of continuous functions with easy-to-encode structure be still PPAD-Complete? Are there known such classes of functions? Commented Sep 12, 2023 at 17:57
• Yes, of course, because you can take an easy to compute Sperner's lemma type coloring, and convert it into a function such that the direction of $x-F(x)$ corresponds to the color at every point. Commented Sep 13, 2023 at 4:25