Complexidade da percolação

No contexto da percolação de ligações em que é um número inteiro positivo, considere o problema de calcular uma aproximação de da percolação crítica dada uma dimensão de treliça e um parâmetro de precisão como entradas. Existem resultados conhecidos sobre a complexidade desse problema?$\mathbb{Z}^d$$d$$2^{-k}$$p_c$$d\in\mathbb{N}$$k\in\mathbb{N}$

O problema é definitivamente no tempo exponencial duplo aleatório e provavelmente no espaço exponencial. O primeiro resultado foi no meu post original abaixo e o segundo na minha atualização.

POST ORIGINAL: Você não pode obter uma boa aproximação por simulação, se estiver disposto a gastar tempo exponencial em e ? O comprimento da entrada é logarítmico em e . Tão claramente que o problema está no tempo exponencial duplo aleatório. Como ninguém sabe como calcular esses valores de maneira eficiente na prática, parece claro que isso não ocorre em tempo exponencial aleatório. Eu ficaria muito surpreso se outros resultados de complexidade fossem conhecidos sobre esse problema.$k$$d$$k$$d$

ATUALIZAÇÃO ADICIONADA: Na verdade, acho que o problema é muito provável no EXPSPACE. Vamos corrigir a dimensão (para facilitar as coisas, e porque eu não entendo bem as sutilezas da percolação em dimensão variável), de modo que a entrada seja apenas . Além disso, digamos que seja dado em unário, para que eu possa eliminar os exponenciais e falar sobre o PSPACE. Eu proponho o seguinte algoritmo.$k$$k$

Primeiro, devemos assumir que há uma classe de funções pseudo-aleatórias que informam se o vínculo nas coordenadas está presente, onde é a semente para a função pseudo-aleatória e para a qual os laços dados por se comportam como laços aleatórios em relação à percolação.$F_\alpha({\mathbf{x}})$$\mathbf{x}$$\alpha$$F$

Agora, suponha que tenhamos um valor fixo da função pseudo-aleatória seed . Considere o seguinte jogo de dois jogadores, que dois jogadores A e B jogo, após ter sido dada uma probabilidade vínculo e uma semente para .$\alpha$$p$$\alpha$$F$

O jogador 1 fornece dois sites e dentro da distância da origem, mas que ainda estão distantes, onde é escolhido para que, se a probabilidade de percolação estiver dentro de da probabilidade crítica de percolação , com alta probabilidade, haverá um cluster de diâmetro próximo à origem ( é chamado um expoente crítico, e acredito que seu valor é conhecido com provas matemáticas). O jogador 1 afirma que existe um caminho de comprimento conectando esses sites a títulos em${\bf a}$${\bf b}$$2^{k\nu}$$\theta(2^{k \nu})$$\nu$$p$$2^{-k}$$p_c$$2^{k\nu}$$\nu$$d$$F_\alpha$e também fornece o site que é o ponto médio desse caminho de comprimento . O jogador 2 afirma que a primeira parte ou a segunda parte desse caminho não está conectada. O jogador 1 responde dando o ponto que afirma ser o ponto médio dessa seção supostamente desconectada do caminho. Os dois jogadores continuam dessa maneira por etapas, até chegarem a um segmento do caminho que consiste em um único vínculo, cuja presença ou ausência é facilmente verificada.$d$$\log d$

Este é um jogo para dois jogadores cujo resultado informa se a probabilidade crítica de percolação está dentro de de e, pelo resultado de que o tempo polinomial alternado está no PSPACE, o resultado deste jogo pode ser calculado no PSPACE. Uma máquina PSPACE poderia então calcular esse resultado para todas as sementes para descobrir qual jogador vence com alta probabilidade: isso se é maior ou menor ou aproximadamente igual a . Em seguida, ele pode fazer uma pesquisa binária em para encontrar . $2^{-k}$$p_c$$\alpha$$p$$p_c-2^{-k}$$p$$p_c$

DESAFIO: Encontre um algoritmo PSPACE (ou EXPSPACE se não for fornecido em unário) sem usar a suposição de que existem boas funções pseudo-aleatórias para percolação.$k$