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