  We prove the EXPTIME-hardness of the validity problem for the basic temporal
logic on Minkowski spacetime with more than one space dimension. We prove this
result for both the lightspeed-or-slower and the slower-than-light
accessibility relations (and for both the irreflexive and the reflexive
versions of these relations). As an auxiliary result, we prove the
EXPTIME-hardness of validity on any frame for which there exists an embedding
of the infinite complete binary tree satisfying certain conditions. The proof
is by a reduction from the two-player corridor-tiling game.
