Relativization of Gurevich’s Conjectures

DOI10.1007/978-3-030-48006-6_7MaRDI QIDQ5049042OpenAlexFDO

Authors Anatole Dahan, Anuj Dawar

Publication date 9 November 2022

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

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

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Recommendations

• On complete problems, relativizations and logics for complexity classes
• Logics for complexity classes
• scientific article; zbMATH DE number 223336
• Further oracles separating conjectures about incompleteness in the finite domain
• scientific article; zbMATH DE number 1678393

Cites work

• scientific article; zbMATH DE number 3814972 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• A second step toward the strong polynomial-time hierarchy
• Equivalence Relations, Invariants, and Normal Forms
• Generalized Quantifiers and Logical Reducibilities
• On total functions, existence theorems and computational complexity
• The polynomial-time hierarchy

Cited in

(1)

• A surprising relationship between descriptive complexity and proof complexity

This page was built for publication: Relativization of Gurevich’s Conjectures

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