Computational complexity of determining which statements about causality hold in different space-time models

DOI10.1016/J.TCS.2008.06.028MaRDI QIDQ949614zbMATH OpenOpenAlexFDO

Authors Vladik Kreinovich, Olga Kosheleva

Publication date 21 October 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.06.028

zbMATH Keywords

computational complexitycausalityspace-timeelementary geometryTarksi's decision procedure

Mathematics Subject Classification ID

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

Recommendations

• Complexity results for structure-based causality.
• Causality in physics and computation
• Space-time isomorphism problem is intractable (NP-hard)
• Publication:4939149
• The computational complexity of structure-based causality

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3115890 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 54162 (Why is no real title available?)
• scientific article; zbMATH DE number 3240363 (Why is no real title available?)
• scientific article; zbMATH DE number 3252012 (Why is no real title available?)
• scientific article; zbMATH DE number 3322923 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• A Contribution to Chronogeometry
• A Physical Characterization of Conformal Transformations of Minkowski Spacetime
• A characterization of plane Lorentz transformations
• Causality Implies the Lorentz Group
• Cone Preserving Mappings for Quadratic Cones Over Arbitrary Fields
• Efficient solving of quantified inequality constraints over the real numbers
• Mappings of spaces with families of cones and space-time transformations
• On distance-preserving transformations of lines in Euclidean three-space
• On null cone preserving mappings
• On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
• Partial cylindrical algebraic decomposition for quantifier elimination
• Real quantifier elimination is doubly exponential
• Spacetime and causal sets
• Sur l'extension aux relations de quelques propriétés des ordres
• Symmetry characterization of Pimenov's spacetime: A reformulation of causality axioms
• The complexity of elementary algebra and geometry
• Universal homogeneous causal sets

Cited in

(6)

• Causal cones, cone preserving transformations and causal structure in special and general relativity
• Space-time isomorphism problem is intractable (NP-hard)
• Metrization Theorem for Space-Times: From Urysohn’s Problem towards Physically Useful Constructive Mathematics
• Causality in physics and computation
• Reconstructing an open order from its closure, with applications to space-time physics and to logic
• From classical infinite space-time CA to a hybrid CA model for natural sciences modeling

Describes a project that uses

Uses Software

• QEPCAD
• RSOLVER

This page was built for publication: Computational complexity of determining which statements about causality hold in different space-time models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q949614)