Affiliation: | a Departamento de Matemáticas, Universidad Simón Bolívar, Apartado 89000, Caracas 1080-A, Venezuela b Department of Mathematics and Computer Science, University of Leicester, Leicester LE1 7RH, UK |
Abstract: | We show how the fact that there is a first-order projection from the problem transitive closure (TC) to some other problem Ω enables us to automatically deduce that a natural game problem,
, whose instances are labelled instances of Ω, is complete for PSPACE (via log-space reductions). Our analysis is strongly dependent upon the reduction from TC to Ω 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. |