On complete problems, relativizations and logics for complexity classes

DOI10.1007/978-3-642-15025-8_11zbMATH Open1287.68062DBLPconf/birthday/Dawar10OpenAlexW1605774068WikidataQ58215532 ScholiaQ58215532MaRDI QIDQ3586004FDOQ3586004

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

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

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)

Cites Work

• Title not available (Why is that?)
• IP = PSPACE
• Generalized Quantifiers and Logical Reducibilities
• Title not available (Why is that?)
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Structure and complexity of relational queries
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equivalence Relations, Invariants, and Normal Forms
• On the structure of sets in NP and other complexity classes
• Database Theory - ICDT 2005
• Computer Science Logic

Cited In (5)

• STACS 2004
• Exotic quantifiers, complexity classes, and complete problems
• Connecting Complexity Classes, Weak Formal Theories, and Propositional Proof Systems (Invited Talk)
• Title not available (Why is that?)
• 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)