<p>Papadimitriou showed that a version of this problem is PPAD-complete in the paper introducing that class, <a href="http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" rel="nofollow">"On the complexity of the parity argument and other inefficient proofs of existence"</a>.</p>

<p>His formulation of the problem is:</p>

<blockquote>
  <p><em>Borsuk-Ulam.</em> Given an integer n and a Turing machine computing for each
  point $P=(x_1,\dots,x_d)$ with $-n\leq x_i\leq n$ and $\max_{|x_i|}=n$ (the surface of the $L_1$ sphere), a function $f(p)$ with $f(p) \leq \frac{1}{Kn}$. Find an $x$ with $|f(x) - f( - x)| \leq \frac{1}{n^2}$.</p>
</blockquote>

<p>(Sidenote -- many times when you see a fixed-point type of theorem, PPAD is a good guess for the complexity of finding it...)</p>

CC BY-SA 4.0
2023-12-14T06:13:53.330Z
But Papadimitriou's proof was incorrect, for PPA-completeness see https://doi.org/10.1016/j.jcss.2019.09.002.
domotorp
CC BY-SA 3.0
2015-08-06T22:05:14.660Z
2015-08-08T11:41:15.867Z
2015-08-08T11:41:15.867Z
usul
<p>How is the oracle given and what do we know about <span class="math-container">$g$</span>?
If the oracle is black-box and we only know that <span class="math-container">$g$</span> is continuous odd, then already for <span class="math-container">$n=1$</span> we might require infinitely many questions...</p>
<p>If the oracle is given by some Turing-machine, then you get that your problem is</p>
<ol>
<li><p>FIXP-complete,</p>
</li>
<li><p>PPA-complete,</p>
</li>
</ol>
<p>where the size of the input is length of <span class="math-container">$\epsilon$</span>.
For an intro into these, see <a href="http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf" rel="nofollow noreferrer">http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf</a> and here where they prove PPA-completeness, correcting the earlier incorrect claim from Papadimitriou that it is in PPAD: <a href="https://doi.org/10.1016/j.jcss.2019.09.002" rel="nofollow noreferrer">https://doi.org/10.1016/j.jcss.2019.09.002</a></p>

CC BY-SA 4.0
2015-08-06T22:09:35.093Z
2023-12-14T06:13:21.357Z
2023-12-14T06:13:21.357Z
domotorp
<p>The <a href="https://en.wikipedia.org/wiki/Borsuk%E2%80%93Ulam_theorem" rel="nofollow">Borsuk-Ulam theorem</a> says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x_0$ such that $g(x_0)=0$. </p>

<p><a href="https://www.math.hmc.edu/~su/papers.dir/tucker.pdf" rel="nofollow">Simmons and Su (2002)</a> describe a method to approximate the point $x_0$ using <a href="https://en.wikipedia.org/wiki/Tucker%27s_lemma" rel="nofollow">Tucker's lemma</a>. However, it is not clear what the run-time complexity of their method is.</p>

<p>Suppose we are given an oracle for the function $g$ and an approximation factor $\epsilon&gt;0$. What is the run-time complexity (as a function of $n$) of:</p>

<ol>
<li>Finding a point $x$ such $|g(x)|&lt;\epsilon$?</li>
<li>Finding a point $x$ such that the $|x-x_0|&lt;\epsilon$, when $x_0$ is a point satisfying $g(x_0)=0$?</li>
</ol>

<approximation-algorithms><time-complexity><topology><algebraic-topology>
The complexity of finding a Borsuk-Ulam point
Erel Segal-Halevi
# The complexity of finding a Borsuk-Ulam point

(Asked by: username_0 on 2015-08-06)

The [Borsuk-Ulam theorem](https://en.wikipedia.org/wiki/Borsuk%E2%80%93Ulam_theorem) says that for every continuous odd function $g$ from an n-sphere into Euclidean n-space, there is a point $x\_0$ such that $g(x\_0)=0$.

[Simmons and Su (2002)](https://www.math.hmc.edu/~su/papers.dir/tucker.pdf) describe a method to approximate the point $x\_0$ using [Tucker's lemma](https://en.wikipedia.org/wiki/Tucker%27s_lemma). However, it is not clear what the run-time complexity of their method is.

Suppose we are given an oracle for the function $g$ and an approximation factor $\epsilon>0$. What is the run-time complexity (as a function of $n$) of:

1. Finding a point $x$ such $|g(x)|<\epsilon$?
2. Finding a point $x$ such that the $|x-x\_0|<\epsilon$, when $x\_0$ is a point satisfying $g(x\_0)=0$?

**Tags:** approximation-algorithms, time-complexity, topology, algebraic-topology


---

## 2 answers

### Answer by username_1 on 2015-08-06. Score: 5 | Accepted answer

Papadimitriou showed that a version of this problem is PPAD-complete in the paper introducing that class, ["On the complexity of the parity argument and other inefficient proofs of existence"](http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf).

His formulation of the problem is:

> *Borsuk-Ulam.* Given an integer n and a Turing machine computing for each
> point $P=(x\_1,\dots,x\_d)$ with $-n\leq x\_i\leq n$ and $\max\_{|x\_i|}=n$ (the surface of the $L\_1$ sphere), a function $f(p)$ with $f(p) \leq \frac{1}{Kn}$. Find an $x$ with $|f(x) - f( - x)| \leq \frac{1}{n^2}$.

(Sidenote -- many times when you see a fixed-point type of theorem, PPAD is a good guess for the complexity of finding it...)

> **Comments:**
> **username_2**: But Papadimitriou's proof was incorrect, for PPA-completeness see https://doi.org/10.1016/j.jcss.2019.09.002.  

---

### Answer by username_2 on 2015-08-06. Score: 6

How is the oracle given and what do we know about $g$?
If the oracle is black-box and we only know that $g$ is continuous odd, then already for $n=1$ we might require infinitely many questions...

If the oracle is given by some Turing-machine, then you get that your problem is

1. FIXP-complete,
2. PPA-complete,

where the size of the input is length of $\epsilon$.
For an intro into these, see <http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf> and here where they prove PPA-completeness, correcting the earlier incorrect claim from Papadimitriou that it is in PPAD: <https://doi.org/10.1016/j.jcss.2019.09.002>


---

