Generalized hex and logical characterizations of polynomial space

DOI10.1016/S0020-0190(97)00116-6zbMath1337.68120arXivmath/9612228OpenAlexW1976089946MaRDI QIDQ287159

Iain A. Stewart, Argimiro Arratia Quesada

Publication date: 26 May 2016

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

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

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

• Methods for proving completeness via logical reductions
• Context-sensitive transitive closure operators
• Completeness of path-problems via logical reductions
• 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
• Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
• Complete problems for fixed-point logics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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