<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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. </p>

<p>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$. </p>

<p>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.</p>

<p>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$.    </p>

<p>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.</p>

CC BY-SA 2.5
2011-02-22T14:20:44.173Z
Perhaps I am misunderstanding what is being asked, but doesn't this amount to determining whether there exists a path between any pair of vertices where one is chosen from each of two sets (say opposite sides of a hypercube for a sufficiently large cube) for various $k$? In this case enumerating disconnected connected subgraphs should give the answer in time polynomial in $d$. You could potentially get a polynomial scaling in $k$ too by using a binary search.
Joe Fitzsimons
CC BY-SA 2.5
2011-02-22T18:53:11.477Z
Let's worry about the simulation only in fixed dimensions (I don't know enough about the behavior of percolation if the dimension is a varying parameter). You want to approximate the critical probability $c_p$ for percolation to within $2^{-k}$. Now, there is a critical exponent $\sigma$ that says that if the percolation probability is at least $c_p-\epsilon$, then the size of the largest cluster is $\epsilon^{-\sigma}$. So to estimate the critical probability to within $2^{-k}$, you need to look at a region of volume something like $2^{k\sigma}$.
Peter Shor 
CC BY-SA 2.5
2011-02-22T18:59:17.350Z
(Comment continued.) I think you may be right in that the algorithm may not need to be exponential in $d$ as well. Let me think about it.
Peter Shor 
CC BY-SA 2.5
2011-02-23T04:35:35.940Z
@Joe: the results I can easily find on high-dimensional percolation may have hidden constants that depend on the dimension in the asymptotic notation. So I really can't say what the dependence on dimension is. I think the EXPSPACE algorithm I give above is likely polynomial in the dimension, but I would need to do a lot more literature search than I want to to decide whether there are theorems that are uniform in the dimension to justify this statement.
Peter Shor 
CC BY-SA 2.5
2011-02-22T13:26:06.810Z
2011-02-23T04:31:13.107Z
2011-02-23T04:31:13.107Z
Peter Shor 
<p>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?</p>

CC BY-SA 2.5
2011-02-22T13:00:51.120Z
Is there any reason to think that $p_c$ is computable even for $\mathbb{Z}^3$?
Colin McQuillan
CC BY-SA 2.5
2011-02-23T09:40:25.120Z
@Colin Computability is not hard to establish.
Al-Alimi
<cc.complexity-theory><randomness><percolation>
Complexity of percolation
Al-Alimi
# Complexity of percolation

(Asked by: username_0 on 2011-02-22)

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?

**Tags:** cc.complexity-theory, randomness, percolation

> **Comments:**
> **username_1**: Is there any reason to think that $p_c$ is computable even for $\mathbb{Z}^3$?  
> **username_0**: @Colin Computability is not hard to establish.  

---

## 1 answers

### Answer by username_2 on 2011-02-22. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_3**: Perhaps I am misunderstanding what is being asked, but doesn't this amount to determining whether there exists a path between any pair of vertices where one is chosen from each of two sets (say opposite sides of a hypercube for a sufficiently large cube) for various $k$? In this case enumerating disconnected connected subgraphs should give the answer in time polynomial in $d$. You could potentially get a polynomial scaling in $k$ too by using a binary search.  
> **username_2**: Let's worry about the simulation only in fixed dimensions (I don't know enough about the behavior of percolation if the dimension is a varying parameter). You want to approximate the critical probability $c_p$ for percolation to within $2^{-k}$. Now, there is a critical exponent $\sigma$ that says that if the percolation probability is at least $c_p-\epsilon$, then the size of the largest cluster is $\epsilon^{-\sigma}$. So to estimate the critical probability to within $2^{-k}$, you need to look at a region of volume something like $2^{k\sigma}$.  
> **username_2**: (Comment continued.) I think you may be right in that the algorithm may not need to be exponential in $d$ as well. Let me think about it.  
> **username_2**: @Joe: the results I can easily find on high-dimensional percolation may have hidden constants that depend on the dimension in the asymptotic notation. So I really can't say what the dependence on dimension is. I think the EXPSPACE algorithm I give above is likely polynomial in the dimension, but I would need to do a lot more literature search than I want to to decide whether there are theorems that are uniform in the dimension to justify this statement.  

---

