O teorema de Borsuk-Ulam diz que para cada função ímpar contínua de uma esfera n para o espaço n euclidiano, existe um ponto tal que .
Simmons e Su (2002) descrevem um método para aproximar o ponto 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 e um fator de aproximação . Qual é a complexidade do tempo de execução (em função de ) de:
- Encontrando um ponto tal ?
- Encontrando um ponto tal que o , quando é um ponto que satisfaz ?
approximation-algorithms
time-complexity
topology
algebraic-topology
Erel Segal-Halevi
fonte
fonte
Respostas:
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 é:
(Sidenote - muitas vezes quando você vê um tipo de teorema de ponto fixo, o PPAD é um bom palpite para a complexidade de encontrá-lo ...)
fonte
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 = 1g g n = 1 podemos exigir infinitas perguntas ...
Se o oráculo é dado por alguma máquina de Turing, você percebe que seu problema é
FIXP-complete,
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 .ϵ
fonte