论文标题
用于拉普拉斯解决方案和扩散方程的复杂性爆炸
Complexity Blowup for Solutions of the Laplace and the Diffusion Equation
论文作者
论文摘要
在本文中，我们研究了溶液对拉普拉斯和扩散方程的计算复杂性。我们表明，对于Laplace和扩散方程的一定类别的初始值问题，解决方案操作员为$ \＃P_1/ \＃P $ -Complete，因为它将其映射到$ \＃p_1/ \＃p $ -complete函数的$ \ \＃p_1/ \＃p_1/ \＃p $ -complete功能。因此，存在多项式时间（Turing）可计算输入数据，因此该解决方案不是多项式时间可计算的，除非$ fp = \＃p $或$ fp_1 = \＃p_1 $。在这种情况下，我们通常不能在数字计算机上模拟拉普拉斯的解或扩散方程的解决方案，而无需具有复杂性爆炸，即，在数字数量中，获得多达有限数量的有限数字的溶液的计算时间可在数字数量上生长出多种多样的数字。这表明建模物理现象的解决方案运算符的计算复杂性本质上很高，与用于近似溶液的数值算法无关。
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_1/ \#P$-complete in the sense that it maps polynomial-time computable functions to the set of $\#P_1/ \#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 $FP_1=\#P_1$. 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.
