On complete problems, relativizations and logics for complexity classes

DOI10.1007/978-3-642-15025-8_11MaRDI QIDQ3586004zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Anuj Dawar

Publication date 3 September 2010

Published in Fields of Logic and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15025-8_11

zbMATH Keywords

descriptive complexityrelativizationoracle complexity classes

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Logics for complexity classes
• Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory
• Capturing Relativized Complexity Classes without Order
• Publication:3030806
• scientific article; zbMATH DE number 4099277

Cites work

• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 4068281 (Why is no real title available?)
• scientific article; zbMATH DE number 559220 (Why is no real title available?)
• scientific article; zbMATH DE number 5485587 (Why is no real title available?)
• Computer Science Logic
• Database Theory - ICDT 2005
• Equivalence Relations, Invariants, and Normal Forms
• Generalized Quantifiers and Logical Reducibilities
• IP = PSPACE
• On the structure of sets in NP and other complexity classes
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Structure and complexity of relational queries

Cited in

(5)

• STACS 2004
• Exotic quantifiers, complexity classes, and complete problems
• Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)
• scientific article; zbMATH DE number 4217898 (Why is no real title available?)
• Logics capturing relativized complexity classes uniformly

This page was built for publication: On complete problems, relativizations and logics for complexity classes

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