Space-time isomorphism problem is intractable (NP-hard) (Q807992)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Space-time isomorphism problem is intractable (NP-hard) |
scientific article |
Statements
Space-time isomorphism problem is intractable (NP-hard) (English)
0 references
1991
0 references
This paper deals with the intractability of the space-time isomorphism problem, i.e. the non-feasibility of the corresponding algorithm in reasonable running time. The local equivalence of space-times in the general non smooth case is viewed here as an isomorphic imbedding of finite space-times (i.e. ``uniform'' spaces with a distance function here assumed to be the proper time between causally ordered events). Considering then the finite causal model as a particular case of the finite oriented graph, the author derives the intractability of the isomorphism problem from that of the ``clique'' problem.
0 references
space-time isomorphism problem
0 references
equivalence of space-times
0 references
causal model
0 references
intractability
0 references