MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider two different infinite graphs, whose vertices are drawn from $\mathbb Z^2$ or $\mathbb Z^3$. Let $P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$ for $d \in \{2,3\}$ be the function such that $P_d(\mathbf x,n)$ to the number of paths (i.e. walks in which every vertex is visited only once; also known in some contexts as a self-avoiding path) of length $n$ from the origin to $\mathbf x \in \mathbb Z$.

From the Wikipedia article on self-avoiding paths, exactly computing [the sum of] $P_d(\mathbf x,n)$ for all $n$ is likely to be difficult if we restrict ourselves to a finite rectangular region of the lattice — the latter problem is conjectured to be NP-hard. However, do we know how $P_d(\mathbf x,n)$ scales, e.g. in terms of the coefficients $x_j$ of $\mathbf x$, as well as $n$?

share|cite|improve this question
Not NP, #P-hard. – domotorp Oct 1 '12 at 19:37
Fair point; perhaps the correct statement would be that determining whether the function exceeds some threshold is conjectured to be NP-hard. I have no intuition either way, and in any case am concerned with asymptotics rather than the exact problem. – Niel de Beaudrap Oct 2 '12 at 0:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.