In this paper, we investigate the computational complexity of solutions to
the Laplace and the diffusion equation. We show that for a certain class of
initial-boundary value problems of the Laplace and the diffusion equation, the
solution operator is
#P1/#P-complete in the sense that it maps
polynomial-time computable functions to the set of
#P1/#P-complete
functions. Consequently, there exists polynomial-time (Turing) computable input
data such that the solution is not polynomial-time computable, unless
FP=#P
or
FP1=#P1. In this case, we can, in general, not simulate the solution of
the Laplace or the diffusion equation on a digital computer without having a
complexity blowup, i.e., the computation time for obtaining an approximation of
the solution with up to a finite number of significant digits grows
non-polynomially in the number of digits. This indicates that the computational
complexity of the solution operator that models a physical phenomena is
intrinsically high, independent of the numerical algorithm that is used to
approximate a solution.