Complexity of percolation In the context of bond percolation on $\mathbb{Z}^d$ where $d$ is a positive integer, consider the problem of computing a $2^{-k}$-approximation of the critical percolation $p_c$ given a lattice dimension $d\in\mathbb{N}$ and a precision parameter $k\in\mathbb{N}$ as inputs. Are there any known results about the complexity of such problem?
The problem is definitely in random double exponential time, and likely in exponential space. The first result was in my original post below, and the second in my update.

ORIGINAL POST:
Can't you get a good approximation by simulation, if you're willing to spend time exponential in $k$ and $d$? The input length is logarithmic in $k$ and $d$. So clearly the problem is in random double exponential time. Since nobody knows how to compute these values efficiently in practice, it seems clear this is not known to be in random exponential time. I would be very surprised if any other complexity results were known about this problem.

ADDED UPDATE: 
Actually, I think the problem is very likely in EXPSPACE. Let's fix the dimension (to make things easier, and because I don't understand the subtleties of percolation in varying dimension well at all) so the input is just $k$. Also, let's say $k$ is given in unary so that I can drop the exponentials and talk about PSPACE. I propose the following algorithm.

First, we must make the assumption that there is a class of pseudorandom functions $F_\alpha({\mathbf{x}})$ which tell you whether the bond at coordinates $\mathbf{x}$ is present, where $\alpha$ is the seed for the pseudorandom function, and for which the bonds given by $F$ behave like random bonds with respect to percolation. 

Now, suppose that we have a fixed value of the pseudorandom function seed $\alpha$. Consider the following two-player game, which two players A and B play, after being given a bond probability $p$ and a seed $\alpha$ for $F$. 

Player 1 gives two sites ${\bf a}$ and ${\bf b}$ within distance $2^{k\nu}$ of the origin, but which are still $\theta(2^{k \nu})$ distance apart, where $\nu$ is chosen so that if the percolation probability $p$ is within $2^{-k}$ of the critical percolation probability $p_c$, then with high probability there will be a cluster of diameter $2^{k\nu}$ near the origin ($\nu$ is called a critical exponent, and I believe its value is known with mathematical proof). Player 1 claims that there is a path of length $d$ connecting these sites with bonds in $F_\alpha$, and also gives the site that is the midpoint of this path of length $d$.  Player 2 then claims that either the first part or the second part of this path is not connected. Player 1 responds by giving the point he claims is the midpoint of this allegedly disconnected section of the path. The two players continue in this way for $\log d$ steps, until they reach a segment of path consisting of a single bond, whose presence or absence is easily verified.

This is a two-player game whose result tells whether the critical percolation probability is within $2^{-k}$ of $p_c$, and by the result that alternating polynomial time is in PSPACE, the outcome of this game can be computed in PSPACE. A PSPACE machine could then compute this outcome for all seeds $\alpha$ to find which player wins with high probability: this will tell him whether $p$ is larger or smaller or approximately equal to $p_c-2^{-k} $. It can then do a binary search on $p$ to find $p_c$.    

CHALLENGE: Find a PSPACE (or EXPSPACE if $k$ is not given in unary) algorithm without using the assumption that there are good pseudorandom functions for percolation.