10
$\begingroup$

The Borsuk-Ulam 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) describe a method to approximate the point $x_0$ using Tucker's 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$?
$\endgroup$
  • 1
    $\begingroup$ Is this on a Real RAM machine? $\;$ $\endgroup$ – user6973 Aug 6 '15 at 20:22
5
$\begingroup$

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".

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...)

$\endgroup$
4
$\begingroup$

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. PPAD-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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.