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

DOI10.1007/BF00671011zbMATH Open0731.53025OpenAlexW2087695187MaRDI QIDQ807992FDOQ807992

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)

Cites Work

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

Cited In (2)

• Title not available (Why is that?)
• Title not available (Why is that?)

   Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• In some curved spaces, one can solve NP-hard problems in polynomial time 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)