×

Computational complexity of determining which statements about causality hold in different space-time models. (English) Zbl 1158.68015

Summary: Causality is one of the most fundamental notions of physics. It is therefore important to be able to decide which statements about causality are correct in different models of space-time. In this paper, we analyze the computational complexity of the corresponding decision problems. In particular, we show that: for Minkowski space-time, the decision problem is as difficult as Tarski’s decision problem for elementary geometry, while for a natural model of primordial space-time, the corresponding decision problem is of the lowest possible complexity among all possible space-time models.

MSC:

68Q25 Analysis of algorithms and problem complexity
03B25 Decidability of theories and sets of sentences
03D15 Complexity of computation (including implicit computational complexity)
83A05 Special relativity

Software:

QEPCAD; RSOLVER
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alexandrov, A. D., On Lorentz transformations, Uspekhi Mathematicheskikh Nauk, 5, 3(37), 187 (1950), (in Russian)
[2] Alexandrov, A. D., A contribution to chronogeometry, Canadian Journal of Mathematics, 19, 1119-1128 (1967) · Zbl 0173.24603
[3] Alexandrov, A. D., Mappings of spaces with families of cones and space-time transformations, Annali di Matematica Pura ed Aplicata, 103, 229-257 (1967)
[4] Alexandrov, A. D.; Ovchinnikova, V. V., Remarks on the foundations of special relativity, Leningrad University Vestnik, 11, 94-110 (1953), (in Russian)
[5] Ben-Or, M.; Kozen, D.; Reif, J., The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, 32, 2, 251-264 (1986) · Zbl 0634.03031
[6] Benz, W., A characterization of plane Lorentz transformations, Journal of Geometry, 10, 45-56 (1977) · Zbl 0376.50007
[7] Benz, W., Geometrische Transformationen (1992), BI Wissenscahftsverlag: BI Wissenscahftsverlag Mannheim · Zbl 0754.51005
[8] H. Busemann, Timelike Spaces, Warszawa, PWN, 1967; H. Busemann, Timelike Spaces, Warszawa, PWN, 1967
[9] Canny, J., Some algebraic and geometric computations in PSPACE, (Proceedings of the 20th Annual ACM Symposium on Theory of Computing (1988), ACM Press), 460-469
[10] Collins, G. E.; Hong, H., Partial cylindrical algebraic decomposition for quantifier elimination, Journal of Symbolic Computation, 12, 3, 299-328 (1991) · Zbl 0754.68063
[11] Davenport, J. H.; Heintz, J., Real quantifier elimination is doubly exponential, Journal of Symbolic Computations, 5, 1/2, 29-35 (1988) · Zbl 0663.03015
[12] M. Droste, Universal homogeneous causal sets, in: R. Kopperman, P. Panangaden, M. Smyth, D. Spreen, J. Webster (Eds.), Computational Structures for Modelling Space, Time and Causality, Dagstuhl Seminar Proceedings, Internationales Begegnungs- und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany, 2006, seminar 06341; M. Droste, Universal homogeneous causal sets, in: R. Kopperman, P. Panangaden, M. Smyth, D. Spreen, J. Webster (Eds.), Computational Structures for Modelling Space, Time and Causality, Dagstuhl Seminar Proceedings, Internationales Begegnungs- und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany, 2006, seminar 06341 · Zbl 1111.83016
[13] Fraissé, R., Sur l’extension aux relations de quelques propriétés des ordres, Annals Scientifiques de l’École Normale Supérieure, 71, 363-388 (1954) · Zbl 0057.04206
[14] Fraissé, R., Sur quelques classifications des systèmes de relations, Publications Scientifiques de l’Université d’Algerie, Série A, 1, 35-182 (1954)
[15] D. Grigoriev, V. Kreinovich, Decidability of different space-time models, Leningrad University, Department of Mathematics and Mechanics, Technical Report, 1973 (in Russian); D. Grigoriev, V. Kreinovich, Decidability of different space-time models, Leningrad University, Department of Mathematics and Mechanics, Technical Report, 1973 (in Russian)
[16] Hodges, W., Model Theory (1993), Cambridge University Press
[17] Kreinovich, V., Symmetry characterization of Pimenov’s spacetime: A reformulation of causality axioms”, International Journal of Theoretical Physics, 35, 2, 341-346 (1996) · Zbl 0846.53071
[18] Kronheimer, E. H.; Penrose, R., On the structure of causal spaces, Proceedings of the Cambridge Philosophical Society, 63, 2, 481-501 (1967) · Zbl 0148.46502
[19] Lester, J. A., On null cone preserving mappings, Proceedings of Cambridge Mathematical Society, 81, 455-462 (1977) · Zbl 0358.50002
[20] Lester, J. A., Cone preserving mappings for quadratic cones over arbitrary fields, Canadian Journal of Mathematics, 29, 1247-1253 (1977) · Zbl 0376.50003
[21] Lester, J. A., A physical characterization of conformal transformations of Minkowski spacetime, Annals of Discrete Mathematics, 18, 567-574 (1983) · Zbl 0507.51004
[22] Lester, J. A., Distance preserving transformations, (Buekenhout, F., Handbook of Incidence Geometry (1995), Elsevier: Elsevier Amsterdam) · Zbl 0555.51010
[23] Misner, C. W.; Thorne, K. S.; Wheeler, J. A., Gravitation (1973), Freeman: Freeman San Francisco, California
[24] Papadimitriou, C. H., Computational Complexity (1994), Addison Wesley: Addison Wesley San Diego · Zbl 0557.68033
[25] R.I. Pimenov, Kinematic spaces: Mathematical Theory of Space-Time, NY, Consultants Bureau, 1970; R.I. Pimenov, Kinematic spaces: Mathematical Theory of Space-Time, NY, Consultants Bureau, 1970 · Zbl 0203.28303
[26] Ratschan, S., Efficient solving of quantified inequality constraints over the real numbers, ACM Transactions on Computational Logic, 7, 4, 723-748 (2006) · Zbl 1367.68270
[27] Renegar, J., On the computational complexity and geometry of the first-order theory of the reals, parts I-III, Journal of Symbolic Computation, 13, 3, 255-352 (1992) · Zbl 0798.68073
[28] Sorkin, R., Spacetime and causal sets, (Dolivo, J.; etal., Relativity and Gravitation: Classical and Quantum (1991), World Scientific: World Scientific Singapore), 150-173 · Zbl 0972.83573
[29] Svozil, K., Connections between deviations from Lorentz transformation and relativistic energy-momentum relation, Europhysics Letters, 2, 83-85 (1986)
[30] Svozil, K., Operational perception of space-time coordinates in a quantum medium, Il Nuovo Cimento, 96B, 127-139 (1986)
[31] A. Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd edn, Berkeley and Los Angeles, 1951; A. Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd edn, Berkeley and Los Angeles, 1951 · Zbl 0044.25102
[32] Vroegindewey, P. G.; Kreinovich, V.; Kosheleva, O., From a connected, partially ordered set of events to a field of time intervals, Foundations of Physics, 10, 5-6, 469-484 (1980)
[33] Zeeman, E. C., Causality implies the Lorentz group, Journal of Mathematical Physics, 5, 490-493 (1964) · Zbl 0133.23205
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.