Logics for complexity classes

DOI10.1093/JIGPAL/JZU027zbMATH Open1407.68192arXiv1312.4652OpenAlexW3103066066MaRDI QIDQ4644504

Author name not available (Why is that?)

Publication date: 8 January 2019

Published in: (Search for Journal in Brave)

Abstract: A new syntactic characterization of problems complete via Turing reductions is presented. General canonical forms are developed in order to define such problems. One of these forms allows us to define complete problems on ordered structures, and another form to define them on unordered non-Aristotelian structures. Using the canonical forms, logics are developed for complete problems in various complexity classes. Evidence is shown that there cannot be any complete problem on Aristotelian structures for several complexity classes. Our approach is extended beyond complete problems. Using a similar form, a logic is developed to capture the complexity class $NPcapcoNP$ which very likely contains no complete problem.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Logics for complexity classes

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