Capturing complexity classes with Lindström quantifiers

DOI10.1007/3-540-58338-6_59MaRDI QIDQ5096870zbMATH OpenOpenAlexFDO

Authors Johann A. Makowsky

Publication date 18 August 2022

Published in Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58338-6_59

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Abstract model theory (03C95) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Capturing relativized complexity classes with Lindström quantifiers
• scientific article; zbMATH DE number 1453080
• scientific article; zbMATH DE number 1272994
• Generalized Quantifiers and Logical Reducibilities
• scientific article; zbMATH DE number 1978903

Cites work

• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 3941493 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1555186 (Why is no real title available?)
• scientific article; zbMATH DE number 223336 (Why is no real title available?)
• scientific article; zbMATH DE number 223337 (Why is no real title available?)
• Classifying the computational complexity of problems
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Definability hierarchies of generalized quantifiers
• Expressibility and Parallel Complexity
• Languages that Capture Complexity Classes
• Logical hierarchies in PTIME
• Relativized alternation and space-bounded computation

Cited in

(5)

• Exotic quantifiers, complexity classes, and complete problems
• My writing
• Linear algebraic quantifiers
• Capturing relativized complexity classes with Lindström quantifiers
• Logics capturing relativized complexity classes uniformly

This page was built for publication: Capturing complexity classes with Lindström quantifiers

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