Relativization of Gurevich’s Conjectures

DOI10.1007/978-3-030-48006-6_7OpenAlexW3030874017MaRDI QIDQ5049042FDOQ5049042

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• The polynomial-time hierarchy
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On total functions, existence theorems and computational complexity
• Generalized Quantifiers and Logical Reducibilities
• Equivalence Relations, Invariants, and Normal Forms
• A second step toward the strong 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)