A note on first-order projections and games.

Abstract

We show how the fact that there is a first-order projection from the problem TC (transitive closure) to some other problem $\Omega$ enables us to automatically deduce that a natural game problem, $\mathcal{LG}(\Omega)$, whose instances are labelled instances of $\Omega$, is complete for PSPACE (via log-space reductions). Our analysis is strongly dependent upon the reduction from TC to $\Omega$ being a logical projection in that it fails should the reduction be, for example, a log-space reduction or a quantifier-free first-order translation.