Towards Applying Computational Complexity to Foundations of Physics

V. Kreinovich ; A. M. Finkelstein

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 63-110

Résumé

In one of his early papers, D. Grigoriev analyzed the decidability and computational complexity of different physical theories. This analysis was motivated by the hope that this analysis would help physicists. In this paper, we survey several similar ideas that may be of help to physicists. We hope that further research may lead to useful physical applications.

Bibliographie

[1] J. D. Barrow, F. J. Tipler, The Anthropic Cosmological Principle, Oxford University Press, Oxford, 1986

[2] V. B. Berestetsky, E. M. Lifshits, Relativistic quantum theory, Pergamon Press, 1974

[3] B. E. Blank, “The Constants of Nature and Just Six Numbers”, Notices of the American Mathematical Society, 51:4 (2004), 1220–1225 | MR

[4] L. Boltzmann, “Bemrkungen über einige Probleme der mechanischen Wärmtheorie”, Wiener Ber., LXXVI (1877), 62–100

[5] L. Brink, M. Henneaux, Principles of String Theory, Plenum Press, 1988 | MR

[6] C. D. Broad, Ethics and the history of philosophy, Routledge and Kegan Paul, London, 1952

[7] R. H. Dicke, “Principle of Equivalence and Weak Interactions”, Rev. Mod. Phys., 29 (1957), 355 | DOI | MR

[8] P. A. M. Dirac, “The cosmological constants”, Nature, 139 (1937), 323 | DOI | Zbl

[9] P. A. M. Dirac, “A new basis for cosmology”, Proceedings of the Royal Society Series A, 165, 1938, 199–208

[10] R. P. Feynman, Statistical Mechanics, W. A. Benjamin, 1972

[11] P. Feynman, R. B. Leighton, M. Sands, The Feynman Lectures, Addison-Wesley, 1965

[12] R. P. Feynman, QED: The Strange Theory of Light and Matter, Princeton University Press, Princeton, 1985

[13] A. M. Finkelstein, V. Kreinovich, “Impossibility of hardly possible events: physical consequences”, Abstr. 8th Int'l Congr. Log., Methodology and Philosophy of Science, v. 5, pt. 2, Moscow, 1987, 23–25 | MR

[14] L. Grover, “A fast quantum mechanical algorithm for database search”, Proc. 28th ACM Symp. on Theory of Computing, 1996, 212–219 | MR | Zbl

[15] L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack”, Phys. Rev. Lett., 79 (1997), 325–328 | DOI

[16] L. Grover, “A framework for fast quantum mechanical algorithms”, Phys. Rev. Lett., 80 (1998), 4329–4332 | DOI | MR

[17] W. Heisenberg, Introduction to the unified field theory of elementary particles, Interscience, London, New York, 1966 | Zbl

[18] F. Herrmann, M. Margenstern, “A universal cellular automaton in the hyperbolic plane”, Theoretical Computer Science, 296:2 (2003), 327–364 | DOI | MR | Zbl

[19] A. N. Kolmogorov, Automata and life Cybernetics expected and Cybernetics unexpected, Nauka, Moscow, 1968 | Zbl

[20] M. Koshelev, “Maximum entropy and acausal processes: astrophysical applications and challenges”, Maximum Entropy and Bayesian Methods, eds. G. J. Erickson et al., Kluwer, Dordrecht, 1998, 253–262 | MR | Zbl

[21] O. M. Kosheleva, V. Kreinovich, On the Algorithmic Problems of a Measurement Process, Research Reports in Philosophy of Physics, University of Toronto, Ontario, Canada, Department of Philosophy, No 5, 1978 | MR

[22] O. M. Kosheleva, V. Kreinovich, “What can physics give to constructive mathematics”, Mathematical Logic and Mathematical Linguistics, Kalinin, 1981, 117–128 | MR

[23] V. Kreinovich, On the possibility of using physical processes when solving hard problems, Leningrad Center for New Information Technology “Informatika”, Technical Report, Leningrad, 1989

[24] V. Kreinovich, “Toward Formalizing Non-Monotonic Reasoning in Physics: the Use of Kolmogorov Complexity and Algorithmic Information Theory to Formalize the Notions ‘Typically’ and ‘Normally’”, Proceedings of the Workshops on Intelligent Computing WIC'04 associated with the Mexican International Conference on Artificial Intelligence MICAI'04 (Mexico City, Mexico, April 26–27), eds. L. Sheremetov, M. Alvarado, 2004, 187–194

[25] V. Kreinovich, I. A. Kunin, “Kolmogorov Complexity and Chaotic Phenomena”, International Journal of Engineering Science, 41:3–5 (2003), 483–493 | DOI | MR | Zbl

[26] V. Kreinovich, I. A. Kunin, “Kolmogorov Complexity: How a Paradigm Motivated by Foundations of Physics Can Be Applied in Robust Control”, Proc. Int'l Conf. “Physics and Control” PhysCon'2003 (St. Petersburg, Russia, August 20–22), eds. A. L. Fradkov, A. N. Churilov, 2003, 88–93

[27] V. Kreinovich, L. Longprè, M. Koshelev, “Kolmogorov complexity, statistical regularization of inverse problems, and Birkhoff's formalization of beauty”, Bayesian Inference for Inverse Problems (San Diego, CA), Proc. SPIE, 3459, ed. A. Mohamad-Djafari, 1998, 159–170

[28] H. E. Kyburg, Jr., Probability and the logic of rational belief, Wesleyan Univ. Press, 1961

[29] S. Lem, Solaris, Harcourt, 2002 | Zbl

[30] M. Li, P. M. B. Vitanyi, An Introduction to Kolmogorov Complexity, Springer, NY, 1997 | Zbl

[31] C. W. Misner, K. S. Thorne, J. A. Wheeler, Gravitation, W. H. Freeman, 1973 | MR

[32] D. Morgenstein, V. Kreinovich, “Which algorithms are feasible and which are not depends on the geometry of space-time”, Geombinatorics, 4:3 (1995), 80–97 | Zbl

[33] M. A. Nielsen, I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000 | MR

[34] “Particle Data Group”, Phys. Lett. B, 170:1 (1986)

[35] Rees, Martin, Just Six Numbers: The Deep Forces that Shape the Universe, Basic Books, New York, 2001 | MR

[36] P. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring”, Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, 124–134 | MR

[37] L. G. Taff, Celestial mechanics: a computational guide for the practitioner, Wiley, 1985

[38] A. Tarski, A decision method for elementary algebra and geometry, Second edition, Berkeley and Los Angeles, 1951

[39] A. N. Tikhonov, V. Y. Arsenin, Solutions of ill-posed problems, V. H. Winston Sons, Washington, DC, 1977 | MR | Zbl

[40] H. M. Wadsworth Jr., Handbook of statistical methods for engineers and scientists, McGraw-Hill, NY, 1990

[41] Ya. B. Zeldovich, I. D. Novikov, Relativistic Astrophysics. Part 2. The structure and evolution of the Universe, The University of Chicago Press, Chicago and London, 1983 | Zbl