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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Sep 12, 2023 at 13:34
  • $\begingroup$ @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? $\endgroup$
    – ntrstd11
    Commented Sep 12, 2023 at 17:57
  • $\begingroup$ 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. $\endgroup$
    – domotorp
    Commented Sep 13, 2023 at 4:25


Your Answer

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