Komplexität der Versickerung

Betrachten Sie im Zusammenhang mit der Bindungsperkolation auf wobei eine positive ganze Zahl ist, das Problem der Berechnung einer -Näherung der kritischen Perkolation bei einer Gitterdimension und ein Präzisionsparameter als Eingaben. Gibt es bekannte Ergebnisse zur Komplexität eines solchen Problems? d 2 - k p c d≤ N k≤$\mathbb{Z}^d$$d$$2^{-k}$$p_c$$d\in\mathbb{N}$$k\in\mathbb{N}$

Das Problem liegt definitiv in der zufälligen doppelten Exponentialzeit und wahrscheinlich im Exponentialraum. Das erste Ergebnis war in meinem ursprünglichen Beitrag unten und das zweite in meinem Update.

ORIGINAL POST: Können Sie durch Simulation keine gute Annäherung erhalten, wenn Sie bereit sind, Zeit exponentiell in und d zu verbringen ? Die Eingangslänge ist in k und d logarithmisch . Das Problem liegt also eindeutig in der zufälligen doppelten Exponentialzeit. Da niemand weiß, wie man diese Werte in der Praxis effizient berechnet, scheint es klar zu sein, dass dies nicht in zufälliger exponentieller Zeit geschieht. Ich wäre sehr überrascht, wenn andere Komplexitätsergebnisse zu diesem Problem bekannt wären.$k$$d$$k$$d$

ADDED UPDATE: Eigentlich denke ich, dass das Problem in EXPSPACE sehr wahrscheinlich ist. Lassen Sie uns die Dimension korrigieren (um die Sache zu vereinfachen und weil ich die Feinheiten der Perkolation in unterschiedlichen Dimensionen überhaupt nicht gut verstehe), sodass die Eingabe nur . Nehmen wir außerdem an, k wird unär angegeben, damit ich die Exponentiale löschen und über PSPACE sprechen kann. Ich schlage den folgenden Algorithmus vor.$k$$k$

Zunächst müssen wir annehmen, dass es eine Klasse von Pseudozufallsfunktionen die Ihnen sagen, ob die Bindung an den Koordinaten x vorhanden ist, wobei α der Keim für die Pseudozufallsfunktion ist und für welche die durch F gegebenen Bindungen verhalten sich in Bezug auf Perkolation wie zufällige Bindungen.$F_\alpha({\mathbf{x}})$$\mathbf{x}$$\alpha$$F$

Nehmen wir nun an, wir haben einen festen Wert des Pseudozufallsfunktionskeims . Betrachten Sie das folgende Zwei-Spieler-Spiel, das zwei Spieler A und B spielen, nachdem sie eine Bindungswahrscheinlichkeit p und einen Startwert α für F erhalten haben .$\alpha$$p$$\alpha$$F$

Spieler 1 gibt zwei Stellen und b innerhalb eines Abstands von 2 k ν vom Ursprung an, die jedoch immer noch θ ( 2 k ν ) voneinander entfernt sind, wobei ν so gewählt wird, dass wenn die Perkolationswahrscheinlichkeit p innerhalb von 2 - k des kritischen Perkolations liegt Wahrscheinlichkeit p c , dann gibt es mit hoher Wahrscheinlichkeit einen Cluster mit einem Durchmesser von 2 k ν in der Nähe des Ursprungs ( ${\bf a}$${\bf b}$$2^{k\nu}$$\theta(2^{k \nu})$$\nu$$p$$2^{-k}$$p_c$$2^{k\nu}$$\nu$wird als kritischer Exponent bezeichnet, und ich glaube, sein Wert ist mit mathematischen Beweisen bekannt. Spieler 1 behauptet, dass es einen Pfad der Länge gibt, der diese Stellen mit Bindungen in F α verbindet , und gibt auch die Stelle an, die der Mittelpunkt dieses Pfades der Länge d ist . Spieler 2 behauptet dann, dass entweder der erste Teil oder der zweite Teil dieses Pfades nicht verbunden ist. Spieler 1 antwortet, indem er den Punkt angibt, von dem er behauptet, er sei der Mittelpunkt dieses angeblich getrennten Abschnitts des Pfades. Die beiden Spieler fahren auf diese Weise für log d- Schritte fort, bis sie einen Pfadsegment erreichen, der aus einer einzelnen Bindung besteht, deren Vorhandensein oder Nichtvorhandensein leicht überprüft werden kann.$d$$F_\alpha$$d$$\log d$

Dies ist ein Zwei-Spieler-Spiel, dessen Ergebnis zeigt, ob die kritische Perkolationswahrscheinlichkeit innerhalb von von p c liegt , und durch das Ergebnis, dass sich die alternierende Polynomzeit in PSPACE befindet, kann das Ergebnis dieses Spiels in PSPACE berechnet werden. Eine PSPACE-Maschine könnte dann dieses Ergebnis für alle Samen α berechnen, um herauszufinden, welcher Spieler mit hoher Wahrscheinlichkeit gewinnt: Dies sagt ihm, ob p größer oder kleiner oder ungefähr gleich p c - 2 - k ist . Es kann dann eine binäre Suche auf p durchführen , um p c zu finden . $2^{-k}$$p_c$$\alpha$$p$$p_c-2^{-k}$$p$$p_c$

HERAUSFORDERUNG: Finden Sie einen PSPACE- Algorithmus (oder EXPSPACE, wenn nicht unär angegeben ist), ohne die Annahme zu verwenden, dass es gute Pseudozufallsfunktionen für die Perkolation gibt.$k$