Complexity Blowup for Solutions of the Laplace and the Diffusion Equation

12/01/2022
by   Aras Bacho, et al.
0

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 #P-complete in the sense that it maps polynomial-time computable functions to the set of #P-complete functions. Consequently, there exists polynomial-time (Turing) computable input data such that the solution is not polynomial-time computable, unless FP=#P. 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 exponentially in the number of digits. This shows 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. This indicates that there is a fundamental problem in simulating physical phenomena on digital hardware.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset