Arithmetical definability and computational complexity

DOI10.1016/j.tcs.2004.03.027zbMath1070.68047OpenAlexW2171255643MaRDI QIDQ1885035

Yassine Hachaïchi

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.03.027

zbMATH Keywords

Bounded arithmeticDescriptive complexityLogic and complexity

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets
• Rudimentary relations and primitive recursion: A toolbox
• An arithmetical characterization of NP
• Capturing complexity classes by fragments of second-order logic
• The polynomial-time hierarchy
• A descriptive complexity approach to the linear hierarchy.
• On uniformity within \(NC^ 1\)
• Theory of Formal Systems. (AM-47)
• Weak Second‐Order Arithmetic and Finite Automata
• Languages that Capture Complexity Classes
• Decision Problems of Finite Automata Design and Related Arithmetics
• Complexity classes and theories of finite models
• A spectrum hierarchy
• Rudimentary Predicates and Relative Computation
• Rudimentary Languages and Second‐Order Logic
• Notes on polynomially bounded arithmetic

This page was built for publication: Arithmetical definability and computational complexity