Abstract
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 it 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. Bibliography: 41 titles.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. D. Barrow and F. J. Tipler, The Anthropic Cosmological Principle. Oxford Univ. Press, Oxford (1986).
V. B. Berestetsky and E. M. Lifshits, Relativistic Quantum Theory. Pergamon Press (1974).
B. E. Blank, “The constants of nature and just six numbers},” Notices Amer. Math. Soc.}, 51, No. 4}, 1220–1225 (200
L. Boltzmann, “Bemerkungen über einige Probleme der mechanischen Wärmtheorie},” Wiener Ber., II}, 75}, 62–100 (187
L. Brink and M. Henneaux, Principles of String Theory. Plenum Press, New York (1988).
C. D. Broad, Ethics and the History of Philosophy. Routledge and Kegan Paul, London (1952).
R. H. Dicke, “Principle of equivalence and weak interactions},” Rev. Modern Phys.}, 29}, 355 (195
P. A. M. Dirac, “The cosmological constants},” Nature}, 139}, 323 (193
P. A. M. Dirac, “A new basis for cosmology},” Proc. R. Soc. London A}, 165}, 199–208 (193
R. P. Feynman, Statistical Mechanics. W.A. Benjamin, Reading, Massachusetts (1972).
P. Feynman, R. B. Leighton, and M. Sands, The Feynman Lectures on Physics. Addison-Wesley, Reading, Massachusetts-London (1965).
R. P. Feynman, QED: The Strange Theory of Light and Matter. Princeton Univ. Press, Princeton (1985).
A. M. Finkelstein and V. Kreinovich, “Impossibility of hardly possible events: physical consequences},” in: Abstracts of the 8th International Congress on Logic. Methodology and Philosophy of Science}, Vol. 5}, Part 2, Moscow (1987}), pp. 23–25.
L. Grover, “A fast quantum mechanical algorithm for database search},” in: Proceedings of the 28th ACM Symposium on Theory of Computing} (1996}), pp. 212–2
L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack},” Phys. Rev. Lett.}, 79}, 325–328 (199
L. Grover, “A framework for fast quantum mechanical algorithms},” Phys. Rev. Lett.}, 80}, 4329–4332 (199
W. Heisenberg, Introduction to the Unified Field Theory of Elementary Particles. Interscience, London-New York (1966).
F. Herrmann and M. Margenstern, “A universal cellular automaton in the hyperbolic plane},” Theoret. Comput. Sci.}, 296, No. 2}, 327–364 (200
A. N. Kolmogorov, “Automata and life},” in: Cybernetics Expected and Cybernetics Unexpected} [in Russian], Nauka, Moscow} (1968}), p.
M. Koshelev, “Maximum entropy and acausal processes: astrophysical applications and challenges},” in: Maximum Entropy and Bayesian Methods}, G. J. Erickson} et al. (eds.)}, Kluwer, Dordrecht} (1998}), pp. 253–262.
O. M. Kosheleva and V. Kreinovich, “On the algorithmic problems of a measurement process},” Research Reports in Philosophy of Physics, Department of Philosophy, University of Toronto, Ontario, Canada}, No. 5} (197
O. M. Kosheleva and V. Kreinovich, “What can physics give to constructive mathematics},” in: Mathematical Logic and Mathematical Linguistics} [in Russian], Kalinin (1981}), pp. 117–1
V. Kreinovich, “On the possibility of using physical processes when solving hard problems},” Technical Report, Leningrad Center for New Information Technology “Informatika,” Leningrad (1989}
V. Kreinovich, “M. Alvarado} (eds.)}, Mexico City (2004}), pp. 187–1
V. Kreinovich and I. A. Kunin, “Kolmogorov complexity and chaotic phenomena},” Internat. J. Engrg. Sci.}, 41, Nos.3-5}, 483–493 (200
V. Kreinovich and I. A. Kunin, “A. N. Churilov} (eds.)}, St. Petersburg (2003}), pp. 88–
V. Kreinovich, L. Longprè, and M. Koshelev, “Kolmogorov complexity, statistical regularization of inverse problems, and Birkhoff’s formalization of beauty},” in: Bayesian Inference for Inverse Problems}, A. Mohamad-Djafari} (ed.)}, Proceedings of SPIE}, Vol. 3459}, San Diego (1998}), pp. 159–170.
H. E. Kyburg, Jr., Probability and the Logic of Rational Belief. Wesleyan Univ. Press, Middletown (1961).
S. Lem, Solaris, Harcourt (2002).
M. Li and P. M. B. Vitanyi, An Introduction to Kolmogorov Complexity. Springer, New York (1997).
C. W. Misner, K. S. Thorne, and J. A. Wheeler, Gravitation, W. H. Freeman, San Francisco (1973).
D. Morgenstein and V. Kreinovich, “Which algorithms are feasible and which are not depends on the geometry of space-time},” Geombinatorics}, 4, No. 3}, 80–97 (199
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge Univ. Press, Cambridge (2000).
“Particle Data Group},” Phys. Lett.}, 170B, No. 1} (198
M. Rees, Just Six Numbers: The Deep Forces that Shape the Universe. Basic Books, New York (2001).
P. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring},” in: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science} (1994}), pp. 124–1
L. G. Taff, Celestial Mechanics: A Computational Guide for the Practitioner. Wiley, New York (1985).
A. Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd edition, Univ. of California Press, Berkeley (1951).
A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-Posed Problems. V. H. Winston & Sons, Washington (1977).
H. M. Wadsworth, Jr., Handbook of Statistical Methods for Engineers and Scientists. McGraw-Hill, New York (1990).
Ya. B. Zeldovich and I. D. Novikov, Relativistic Astrophysics. Part 2. The Structure and Evolution of the Universe. The Univ. of Chicago Press, Chicago (1983).
Author information
Authors and Affiliations
Additional information
Published in Zapiski Nauchnykh Seminarov POMI, Vol. 316, 2004, pp. 63–110.
Rights and permissions
About this article
Cite this article
Kreinovich, V., Finkelstein, A.M. Towards applying computational complexity to foundations of physics. J Math Sci 134, 2358–2382 (2006). https://doi.org/10.1007/s10958-006-0113-y
Received:
Issue Date:
DOI: https://doi.org/10.1007/s10958-006-0113-y