On the computational complexity of the Dirichlet problem for Poisson’s equation. (English) Zbl 1456.03069
Summary: The last years have seen an increasing interest in classifying (existence claims in) classical mathematical theorems according to their strength. We pursue this goal from the refined perspective of computational complexity. Specifically, we establish that rigorously solving the Dirichlet Problem for Poisson’s Equation is in a precise sense ‘complete’ for the complexity class \(\#\mathcal{P}\) and thus as hard or easy as parametric Riemann integration [H. Friedman, Adv. Math. 53, 80–98 (1984; Zbl 0563.03023); K.-I Ko, Complexity theory of real functions. Boston, MA etc.: Birkhäuser (1991; Zbl 0791.03019)].
MSC:
| 03D78 | Computation over the reals, computable analysis |
| 03D15 | Complexity of computation (including implicit computational complexity) |
| 03F60 | Constructive and recursive analysis |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 28A50 | Integration and disintegration of measures |
References:
| [1] | BlumensonL.E. (1960). Classroom notes: A derivation of n-Dimensional spherical coordinates. The American Mathematical Monthly67(1)63-66.10.2307/2308932 · doi:10.2307/2308932 |
| [2] | BournezO., GraçaD.S., PoulyA. and ZhongN. (2013). Computability and computational complexity of the evolution of nonlinear dynamical systems. In: Proc. 9th Conference on Computability in Europe (CiE 2013), Springer LNCS vol. 7921, doi 10.1007/978-3-642-39053-1_2. · Zbl 1387.68131 |
| [3] | BrattkaV. and YoshikawaA. (2006). Towards computability of elliptic boundary value problems in variational formulation. Journal of Complexity, 22858-880.10.1016/j.jco.2006.04.007 · Zbl 1126.03052 |
| [4] | BravermanM. (2005). On the complexity of real functions. In: Proc. 6th Annual IEEE Symposium on Foundations of Computer Science, doi 10.1109/SFCS.2005.58. |
| [5] | FriedmanH. (1984). The computational complexity of maximization and integration. Advances in Mathematics53(1)80-98.10.1016/0001-8708(84)90019-7 · Zbl 0563.03023 · doi:10.1016/0001-8708(84)90019-7 |
| [6] | GareyM.R. and JohnsonD.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York. · Zbl 0411.68039 |
| [7] | GilbargD. and TrudingerN.S. (2001). Elliptic Partial Differential Equations of Second Order, Classics in Mathematics. Springer-Verlag, Berlin. Reprint of the 1998 edition. · Zbl 0691.35001 |
| [8] | GrzegorczykA. (1957). On the definitions of computable real continuous functions. Fundamenta Mathematicae4461-71. · Zbl 0079.24801 |
| [9] | KawamuraA. (2010). Lipschitz continuous ordinary differential equations are polynomial-space complete. Computational Complexity19(2)305-332.10.1007/s00037-010-0286-0 · Zbl 1232.03031 · doi:10.1007/s00037-010-0286-0 |
| [10] | KawamuraA. (2011). Computational Complexity in Analysis and Geometry. PhD thesis, University of Toronto. |
| [11] | KawamuraA. and CookS. (2012). Complexity theory for operators in analysis. ACM Transactions in Computation Theory4(2) Article 5. · Zbl 1322.68083 |
| [12] | KawamuraA., OtaH., RösnickC. and ZieglerM. (2014). Computational complexity of smooth differential equations. Logical Methods in Computer Science10(1)6. · Zbl 1325.68100 |
| [13] | KoK.-I. (1982). The maximum value problem and NP real numbers. Journal of Computer and System Sciences24(1)15-35.10.1016/0022-0000(82)90053-8 · Zbl 0481.03038 · doi:10.1016/0022-0000(82)90053-8 |
| [14] | KoK.-I. (1990). Inverting a one-to-one real function is inherently sequential. In: Feasible Mathematics (Ithaca, NY, 1989), Progress in Computer Science and Applied Logic, volume 9, Birkhäuser Boston, Boston, MA239-257. · Zbl 0765.68052 |
| [15] | KoK.-I. (1991). Complexity Theory of Real Functions. Progress in Theoretical Computer Science. Birkhäuser Boston Inc., Boston, MA. · Zbl 0791.03019 |
| [16] | KoK.-I. (1992). On the computational complexity of integral equations. Annals of Pure and Applied Logic53(3)201-228. · Zbl 0760.68036 |
| [17] | KoK.-I. (1998). Polynomial-time computability in analysis. In: Handbook of Recursive Mathematics, Vol. 2, Studies in Logic and the Foundations of Mathematics, volume 139, North-Holland, Amsterdam1271-1317. · Zbl 0938.03090 |
| [18] | KoK.-I. and FriedmanH. (1982). Computational complexity of real functions. Theoretical Computer Sciences20(3), 323-352.10.1016/S0304-3975(82)80003-0 · Zbl 0498.03047 |
| [19] | KoK.-I. and YuF. (2008). On the complexity of convex hulls of subsets of the two-dimensional plane. In: Proceedings of the 4th International Conference on Computability and Complexity in Analysis (CCA 2007). Electron. Notes Theor. Comput. Sci. 202 Elsevier Sci. B. V., Amsterdam121-135. · Zbl 1262.03083 |
| [20] | LabhallaS., LombardiH. and MoutaiE. (2001). Espaces métriques rationnellement présentés et complexité. Theoretical Computer Science250265-332. le cas de l’espace des fonctions réelles uniformément, continues sur un intervalle compact.10.1016/S0304-3975(99)00139-5 · Zbl 0952.68068 |
| [21] | LacombeD. (1958). Sur les possibilités d’extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles. In: Le raisonnement en mathématiques et en sciences expérimentales, Colloques Internationaux du Centre National de la Recherche Scientifique, LXX, Editions du Centre National de la Recherche Scientifique, Paris 67-75. · Zbl 0088.25101 |
| [22] | MoreraG. (1887). Sulle derivate seconde della funzione potenziale di spazio. Rendiconti20302-310. · JFM 19.1036.01 |
| [23] | MüllerN.T. (1987). Uniform computational complexity of Taylor series. In: Proceeding 14th International Colloquium on Automata, Languages, and Programming. Springer-Verlag Lecture Notes in Computer Science267435-444. · Zbl 0645.03060 |
| [24] | MüllerN.T. (1995). Constructive aspects of analytic functions. In: Proc. Workshop on Computability and Complexity in Analysis, volume 190 of InformatikBerichte, FernUniversität Hagen 105-114. |
| [25] | ParberryI. and SchnitgerG. (1988). Parallel computation with threshold functions. Journal of Computer and System Sciences36278-302.10.1016/0022-0000(88)90030-X · Zbl 0652.68064 |
| [26] | Pour-ElM.B. and RichardsJ.I. (1989). Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin. · Zbl 0678.03027 |
| [27] | RösnickC. (2013). Closed sets and operators thereon: Representations, computability and complexity. In: Proceedings of the 10th International Conference on Computability and Complexity in Analysis (CCA), 8-10 July 2013, Nancy, France. |
| [28] | SunS., ZhongN. and ZieglerM. (2015). Computability of navier-stokes’ equation. In: Proceeding of the 11th Conference on Computability in Europe, Lecture Notes in Computer Science9136334-342. · Zbl 1461.03046 |
| [29] | TodaS. (1991). PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing20(5)865-877.10.1137/0220053 · Zbl 0733.68034 · doi:10.1137/0220053 |
| [30] | TuringA. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society42(2)230-265. · JFM 62.1059.03 |
| [31] | WeihrauchK. (2000). Computable Analysis. An Introduction. Springer, Berlin/Heidelberg. · Zbl 0956.68056 |
| [32] | WeihrauchK. and ZhongN. (2002). Is wave propagation computable or can wave computers beat the Turing machine?. Proceedings of London Mathematical Society85(2)312-332.10.1112/S0024611502013643 · Zbl 1011.03035 |
| [33] | WeihrauchK. and ZhongN. (2005). Computing the solution of the Korteweg-de Vries equation with arbitrary precision on turing. Theoretical Computer Science332(1-3)337-366.10.1016/j.tcs.2004.11.005 · Zbl 1079.03034 |
| [34] | WeihrauchK. and ZhongN. (2006). An algorithm for computing fundamental solutions. SIAM Journal on Computing35(6)1283-1294.10.1137/S0097539704446360 · Zbl 1103.03061 |
| [35] | WeihrauchK. and ZhongN. (2007). Computable analysis of the abstract Cauchy problem in a Banach space and its applications I. Mathematical Logic Quarterly53(4-5)511-531.10.1002/malq.200710015 · Zbl 1128.03052 |
| [36] | WienholtzE., KalfH. and KriecherbauerT. (2009). Elliptische Differentialgleichungen zweiter Ordnung. Springer, Dordrecht. Eine Einführung mit historischen Bemerkungen. [An introduction with historical remarks]. · Zbl 1191.35001 |
| [37] | ZhongN. (1998). Derivatives of computable functions. Mathematical Logic Quarterly44304-316.10.1002/malq.19980440303 · Zbl 0908.03045 · doi:10.1002/malq.19980440303 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
