Given integers $d$ and $l$, compute the number of grid points $x \in N^d$ that satisfy $\sum_i x_i^2 \leq l$ (i.e. $||x||_2^2 \leq l$). (Think of $l$ as $r^2$).The problem is obviously in #P. Is it in P or a smaller class? What if in place of $l_2$ we use $l_p$?
Number of grid points in d-dimensional sphere of radius r
algorithms;complexity theory;computational geometry