Space-time isomorphism problem is intractable (NP-hard)

DOI10.1007/BF00671011MaRDI QIDQ807992zbMATH OpenOpenAlexFDO

Authors Vladik Kreinovich

Publication date 1991

Published in International Journal of Theoretical Physics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00671011

zbMATH Keywords

intractabilitycausal modelequivalence of space-timesspace-time isomorphism problem

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25) Local differential geometry of Lorentz metrics, indefinite metrics (53B30) Classes of solutions; algebraically special solutions, metrics with symmetries for problems in general relativity and gravitational theory (83C20)

Recommendations

• scientific article; zbMATH DE number 6482141
• EXPTIME-hardness of higher-dimensional Minkowski spacetime
• In some curved spaces, one can solve NP-hard problems in polynomial time
• scientific article; zbMATH DE number 866044
• Modern space-time and undecidability
• The isomorphism conjecture for NP
• Computational complexity of determining which statements about causality hold in different space-time models
• The Null Space Problem I. Complexity
• Publication:3200187
• scientific article; zbMATH DE number 4154700

Cites work

• scientific article; zbMATH DE number 4173812 (Why is no real title available?)
• scientific article; zbMATH DE number 3703577 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3252012 (Why is no real title available?)
• Birkhoff theorem in a metric theory of gravitation.

Cited in

(3)

• scientific article; zbMATH DE number 6482141 (Why is no real title available?)
• scientific article; zbMATH DE number 903281 (Why is no real title available?)
• Computational complexity of determining which statements about causality hold in different space-time models

This page was built for publication: Space-time isomorphism problem is intractable (NP-hard)

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