A second-order system for polytime reasoning based on Grädel's theorem.
From MaRDI portal
Publication:1412837
DOI10.1016/S0168-0072(03)00056-3zbMath1036.03042MaRDI QIDQ1412837
Antonina Kolokolova, Stephen A. Cook
Publication date: 25 November 2003
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Second- and higher-order arithmetic and fragments (03F35) Descriptive complexity and finite models (68Q19)
Related Items (2)
Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ On the finite axiomatizability of
Cites Work
- Functional interpretations of feasibly constructive arithmetic
- Descriptive characterizations of computational complexity
- Bounded arithmetic and the polynomial hierarchy
- Capturing complexity classes by fragments of second-order logic
- The polynomial-time hierarchy
- Relating the bounded arithmetic and polynomial time hierarchies
- On uniformity within \(NC^ 1\)
- Relational queries computable in polynomial time
- Notes on polynomially bounded arithmetic
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A second-order system for polytime reasoning based on Grädel's theorem.
