Capturing Relativized Complexity Classes without Order

DOI10.1002/MALQ.19980440108MaRDI QIDQ4379631zbMATH OpenOpenAlexWikidataFDO

Authors Anuj Dawar, Georg Gottlob, Lauri Hella

Publication date 30 March 1998

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19980440108

zbMATH Keywords

finite model theoryLindström quantifiersordered structuresrelativized complexity classes

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 3885883
• scientific article; zbMATH DE number 4011940
• Capturing relativized complexity classes with Lindström quantifiers
• scientific article; zbMATH DE number 4106269
• Qualitative relativizations of complexity classes
• Refining Nondeterminism in Relativizations of Complexity Classes
• scientific article; zbMATH DE number 4077187
• Logics capturing relativized complexity classes uniformly
• On the relative complexity of hard problems for complexity classes without complete problems
• Quantitative Relativizations of Complexity Classes

Cited in

(3)

• On complete problems, relativizations and logics for complexity classes
• The complexity class θp2: Recent results and applications in AI and modal logic
• Explanations for query answers under existential rules

This page was built for publication: Capturing Relativized Complexity Classes without Order

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