A complexidade de encontrar um ponto de Borsuk-Ulam

10

O teorema de Borsuk-Ulam diz que para cada função ímpar contínua g de uma esfera n para o espaço n euclidiano, existe um ponto x0 tal que g(x0)=0 .

Simmons e Su (2002) descrevem um método para aproximar o ponto x0 usando o lema de Tucker . No entanto, não está claro qual é a complexidade do tempo de execução do método.

Suponha que recebamos um oráculo para a função g e um fator de aproximação ϵ>0 . Qual é a complexidade do tempo de execução (em função de n ) de:

  1. Encontrando um ponto x tal |g(x)|<ϵ ?
  2. Encontrando um ponto x tal que o |xx0|<ϵ , quando x0 é um ponto que satisfaz g(x0)=0 0 ?
Erel Segal-Halevi
fonte
11
Isso está em uma máquina com RAM real ?

Respostas:

5

Papadimitriou mostrou que uma versão desse problema está completa no PPAD no artigo que apresenta essa classe, "Sobre a complexidade do argumento de paridade e outras provas ineficientes da existência" .

Sua formulação do problema é:

Borsuk-Ulam. Dado um número inteiro n e uma máquina de Turing computando para cada ponto com - n x in e max | x i | = n (a superfície da esfera L 1 ), uma função f ( p ) com f ( p ) P=(x1 1,,xd)-nxEunmax|xEu|=neu1 1f(p) . Encontre umxcom| f(x)-f(-x)| f(p)1 1Knx|f(x)-f(-x)|1 1n2 .

(Sidenote - muitas vezes quando você vê um tipo de teorema de ponto fixo, o PPAD é um bom palpite para a complexidade de encontrá-lo ...)

usul
fonte
4

Como o oráculo é dado e o que sabemos sobre ? Se o oráculo é caixa preta e sabemos apenas que g é ímpar contínuo, então já para n = 1ggn=1 1 podemos exigir infinitas perguntas ...

Se o oráculo é dado por alguma máquina de Turing, você percebe que seu problema é

  1. FIXP-complete,

  2. PPAD-completo,

onde o tamanho da entrada é comprimento de . Para obter uma introdução, consulte http://homepages.inf.ed.ac.uk/kousha/dagstuhl14-etessami-tutorial-equilibrium.pdf .ϵ

domotorp
fonte