Generalized hex and logical characterizations of polynomial space

Abstract: We answer a question posed by Makowsky and Pnueli and show that the logic

(p m m b o x H E X)^{a} s t [m b o x {F O}_{s}]

, where HEX is the operator (i.e., uniform sequence of Lindstr"om quantifiers) corresponding to the well-known {�f PSPACE}-complete decision problem Generalized Hex, collapses to the fragment

m b o x {H E X}^{1} [m b o x {F O}_{s}]

and, moreover, that this logic has a particular normal form which results in the problem HEX being complete for {�f 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, $(p m m b o x T C)^{a} s t [m b o x {F O}_{s}]$ , has such a normal form; which is surprising given that $(p m m b o x H E X)^{a} s t [m b o x {F O}_{s}]$ captures {�f PSPACE} and $(p m m b o x T C)^{a} s t [m b o x {F O}_{s}]$ captures {�f NL}. We also show that $(p m m b o x H E X)^{a} s t [m b o x F O]$ does not capture {�f PSPACE} and that this logic does not have a corresponding normal form.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Generalized hex and logical characterizations of polynomial space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287159)