Generalized Hex and logical characterizations of polynomial space
| dc.creator | Arratia-Quesada, Argimiro A. | |
| dc.creator | Stewart, Iain A. | |
| dc.date | 1996-12-01 | |
| dc.date.accessioned | 2026-07-07T09:15:41Z | |
| dc.date.available | 2026-07-07T09:15:41Z | |
| dc.description | We answer a question posed by Makowsky and Pnueli and show that the logic $(\pm\mbox{HEX})^\ast[\mbox{FO}_s]$, where HEX is the operator (i.e., uniform sequence of Lindström quantifiers) corresponding to the well-known {\bf PSPACE}-complete decision problem Generalized Hex, collapses to the fragment $\mbox{HEX}^1[\mbox{FO}_s]$ and, moreover, that this logic has a particular normal form which results in the problem HEX being complete for {\bf PSPACE} via quantifier-free projections with successor (HEX is the first ``natural'' problem to be shown to have this property). Our proof of this normal form result is remarkably similar to Immerman's original proof that transitive closure logic, $(\pm\mbox{TC})^\ast[\mbox{FO}_s]$, has such a normal form; which is surprising given that $(\pm\mbox{HEX})^\ast[\mbox{FO}_s]$ captures {\bf PSPACE} and $(\pm\mbox{TC})^\ast[\mbox{FO}_s]$ captures {\bf NL}. We also show that $(\pm\mbox{HEX})^\ast[\mbox{FO}]$ does not capture {\bf PSPACE} and that this logic does not have a corresponding normal form. | |
| dc.identifier | https://arxiv.org/abs/math/9612228 | |
| dc.identifier | http://arxiv.org/abs/math/9612228 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/153103 | |
| dc.subject | Logic | |
| dc.title | Generalized Hex and logical characterizations of polynomial space | |
| dc.type | text |