Generalized hex and logical characterizations of polynomial space

DOI10.1016/S0020-0190(97)00116-6zbMATH Open1337.68120arXivmath/9612228OpenAlexW1976089946MaRDI QIDQ287159FDOQ287159

Authors: Iain Stewart, A. A. Arratia-Quesada 

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Abstract: We answer a question posed by Makowsky and Pnueli and show that the logic $(pmmboxHEX{)}^{a}st[mbox{FO}_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 $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 {�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, $(pmmboxTC{)}^{a}st[mbox{FO}_s]$, has such a normal form; which is surprising given that $(pmmboxHEX{)}^{a}st[mbox{FO}_s]$ captures {�f PSPACE} and $(pmmboxTC{)}^{a}st[mbox{FO}_s]$ captures {�f NL}. We also show that $(pmmboxHEX{)}^{a}st[mboxFO]$ does not capture {�f PSPACE} and that this logic does not have a corresponding normal form.

Full work available at URL: https://arxiv.org/abs/math/9612228

Recommendations

• Logical characterization of recognizable sets of polynomials over a finite field
• Generalized hexagons and polar spaces
• The polyadic generalization of the Boolean axiomatization of fields of sets
• scientific article; zbMATH DE number 3993586
• Polynomial operator representations of functions of \(k\)-valued logic
• scientific article; zbMATH DE number 4197920
• A polynomial characterization of Hilbert spaces
• Publication:4723705
• Publication:3496494
• On the superstructure of the class of polynomials in multivalued logics

zbMATH Keywords

computational complexityfinite model theorycompleteness via logical reductionsdescriptive complexitylogical characterizations of polynomial space

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Cites Work

• Title not available (Why is that?)
• Context-sensitive transitive closure operators
• Completeness of path-problems via logical reductions
• Title not available (Why is that?)
• Title not available (Why is that?)
• An application of games to the completeness problem for formalized theories
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Languages that Capture Complexity Classes
• Title not available (Why is that?)
• Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complete problems for fixed-point logics
• Title not available (Why is that?)
• Methods for proving completeness via logical reductions

Cited In (3)

• Computer Science Logic
• On the Descriptive Complexity of a Simplified Game of Hex
• Computer Science Logic

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)