<p>I'm studying the complexity class PPAD (from the <a href="https://dl.acm.org/doi/10.1016/S0022-0000(05)80063-7" rel="nofollow noreferrer">seminal 1994 work by Papadimitriou</a>) 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 <a href="https://en.wikipedia.org/wiki/Brouwer_fixed-point_theorem" rel="nofollow noreferrer">computational Brouwer problem</a>, and the representation of a continuous function <span class="math-container">$F: K \rightarrow K$</span> as an input to a Turing machine, where <span class="math-container">$K$</span> is a closed convex domain.</p>
<ol>
<li><p>The <a href="https://en.wikipedia.org/wiki/Brouwer_fixed-point_theorem" rel="nofollow noreferrer">Brouwer problem</a> seems to be challenging to define since the problem would require as input a Lipschitz function <span class="math-container">$F$</span>, 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 <span class="math-container">$x - F(x)$</span> 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 <em>strictly harder</em> than PPAD-complete problems, since continuous functions where such a succinct Boolean circuit exists is a subset of all Lipschitz continuous functions on <span class="math-container">$K$</span>?</p>
</li>
<li><p>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 <span class="math-container">$\sin x, \max(x, y),\ldots$</span>, or continuous functions that can be represented succinctly as a computational graph, or a L-layer W-width ReLU neural network, etc.</p>
</li>
</ol>

CC BY-SA 4.0
2023-09-12T13:34:53.723Z
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 https://en.wikipedia.org/wiki/Matroid_oracle.
domotorp
CC BY-SA 4.0
2023-09-12T17:57:19.943Z
@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?
ntrstd11
CC BY-SA 4.0
2023-09-13T04:25:48.880Z
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.
domotorp
<cc.complexity-theory><ppad><nash-equilibrium>
Encoding of continuous functions in PPAD
ntrstd11
# Encoding of continuous functions in PPAD

(Asked by: username_0 on 2023-09-11)

I'm studying the complexity class PPAD (from the [seminal 1994 work by Papadimitriou](https://dl.acm.org/doi/10.1016/S0022-0000(05)80063-7)) 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](https://en.wikipedia.org/wiki/Brouwer_fixed-point_theorem), 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](https://en.wikipedia.org/wiki/Brouwer_fixed-point_theorem) 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.

**Tags:** cc.complexity-theory, ppad, nash-equilibrium
> **Comments:**
> **username_1**: 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 https://en.wikipedia.org/wiki/Matroid_oracle.  
> **username_0**: @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?  
> **username_1**: 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.  

---

## 0 answers

