解决拉普place 和分化解决方案的复杂吹爆 (Complexity Blowup for Solutions of the Laplace and the Diffusion Equation)

from arxiv, The results of this paper on simulating physical theories on digital computers influenced the article of Holger Boche und Frank Fitzek "Metaverse at the campfire of the future" in Germany's major newspaper, the Frankfurter Allgemeine Zeitung (FAZ) (URL: https://www.faz.net/-ikh-aqw8x). Technological challenges for the design of the Metaverse are discussed in this article

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 unbounded as a mapping from the space of polynomial-time computable functions into itself in the sense that 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 is intrinsically high, independent of the numerical algorithm that is used to obtain a solution. This indicates that there is a fundamental problem in computing a solution on a digital hardware.

翻译：在本文中, 我们调查 Laplace 解决方案的计算复杂性和扩散方程式。我们显示, 对于 Laplace 和扩散方程式的某类初始边界值问题和扩散方程式, 解决方案操作员没有被限制为从多球- 多球- 时间计算函数空间的映射到自己, 也就是说, 存在多球- 计算时( 试算) 可计算输入数据, 使得解决方案不是多球- 时间计算, 除非$FP ⁇ P$。在这种情况下, 一般来说, 我们无法模拟 Laplace 的解决方案或数字计算机上的扩散方程式, 而没有复杂的爆炸, 也就是说, 计算出一个解决方案的近似时间, 在数字数中, 数量有限的数字数成倍增长。这表明, 解决方案操作员的计算复杂性本质上很高, 独立于用于获得解决方案的数字算法。这说明计算数字硬件的解决方案存在根本性问题。