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

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.