Logics for complexity classes

DOI10.1093/JIGPAL/JZU027MaRDI QIDQ4644504zbMATH OpenOpenAlexFDO

Authors Vladimir Naidenko

Publication date 8 January 2019

Published in Logic Journal of the IGPL (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycompletenesstheory of computationdescriptive complexityTuring reduction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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.

Recommendations

• scientific article; zbMATH DE number 4103047
• Logical and schematic characterization of complexity classes
• Computational complexity and the expressive power of logics
• Logics which capture complexity classes over the reals
• Logics which capture complexity classes over the reals
• Proof Complexity of Non-classical Logics
• Proof complexity of non-classical logics
• Logics for Computer Science
• Logics capturing relativized complexity classes uniformly
• scientific article; zbMATH DE number 3995647

Cited in

(23)

• scientific article; zbMATH DE number 1424044 (Why is no real title available?)
• Applicative theories for logarithmic complexity classes
• Complete problems in the first-order predicate calculus
• On completeness for NP via projection translations
• Complete Problems for Higher Order Logics
• STACS 2004
• Universal first-order logic is superfluous in the second level of the polynomial-time hierarchy
• Descriptive characterizations of computational complexity
• Complexity Classifications for Logic-Based Argumentation
• A recipe for the complexity analysis of non-classical logics
• Methods for proving completeness via logical reductions
• Universal first-order logic is superfluous for NL, P, NP and coNP
• Parameterized Complexity Classes under Logical Reductions
• Approximate formulae for a logic that capture classes of computational complexity
• On complete problems, relativizations and logics for complexity classes
• Logical operations and Kolmogorov complexity
• From almost optimal algorithms to logics for complexity classes via listings and a halting problem
• First-order reduction and computational complexity
• Gap-languages and log-time complexity classes
• scientific article; zbMATH DE number 4103047 (Why is no real title available?)
• Logics which capture complexity classes over the reals
• The complexity of \(\mathit{AUTOSAT}(\Sigma^i_m)\)
• Logics capturing relativized complexity classes uniformly

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)