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

DOI10.1007/BF00671011zbMATH Open0731.53025OpenAlexW2087695187MaRDI QIDQ807992FDOQ807992

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Birkhoff theorem in a metric theory of gravitation.
• Title not available (Why is that?)

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)