A note on first-order projections and ga
✍
Argimiro A. Arratia; Iain A. Stewart
📂
Article
📅
2003
🏛
Elsevier Science
🌐
English
⚖ 114 KB
We show how the fact that there is a ÿrst-order projection from the problem transitive closure (TC) to some other problem enables us to automatically deduce that a natural game problem, LG( ), whose instances are labelled instances of , is complete for PSPACE (via log-space reductions). Our analysis