Computational complexity of determining which statements about causality hold in different space-time models
Causality is one of the most fundamental notions of physics. It is therefore important to be able to decide which statements about Causality are correct in different models of space-time. In this paper. we analyze the computational complexity of the corresponding decision problems. In particular, we show that: for Minkowski space-time, the decision problem is as difficult as Tarski's decision problem for elementary geometry, while for a natural model of primordial space-time, the corresponding decision problem is of the lowest possible complexity among all possible space-time models. (c) 2008 Elsevier B.V. All rights reserved.
computational complexity causality space-time elementary geometry tarksi's decision procedure