Arithmetical definability and computational complexity

DOI10.1016/J.TCS.2004.03.027MaRDI QIDQ1885035zbMATHOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1670480
• Descriptive characterizations of computational complexity
• Bounded arithmetic for NC, ALogTIME, L and NL
• A Characterisation of Definable NP Search Problems in Peano Arithmetic
• scientific article; zbMATH DE number 1540059

Cites work

• scientific article; zbMATH DE number 4066875 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• scientific article; zbMATH DE number 3186872 (Why is no real title available?)
• A descriptive complexity approach to the linear hierarchy.
• A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets
• A spectrum hierarchy
• An arithmetical characterization of NP
• Capturing complexity classes by fragments of second-order logic
• Complexity classes and theories of finite models
• Decision Problems of Finite Automata Design and Related Arithmetics
• Languages that Capture Complexity Classes
• Notes on polynomially bounded arithmetic
• On uniformity within \(NC^ 1\)
• Rudimentary Languages and Second‐Order Logic
• Rudimentary Predicates and Relative Computation
• Rudimentary relations and primitive recursion: A toolbox
• The polynomial-time hierarchy
• Theory of Formal Systems. (AM-47)
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(12)

• Many Facets of Complexity in Logic
• scientific article; zbMATH DE number 1531922 (Why is no real title available?)
• Arithmetic definability by formulas with two quantifiers
• scientific article; zbMATH DE number 5267925 (Why is no real title available?)
• scientific article; zbMATH DE number 3966052 (Why is no real title available?)
• A note on definability in fragments of arithmetic with free unary predicates
• scientific article; zbMATH DE number 1985597 (Why is no real title available?)
• scientific article; zbMATH DE number 3931010 (Why is no real title available?)
• scientific article; zbMATH DE number 424614 (Why is no real title available?)
• scientific article; zbMATH DE number 1670480 (Why is no real title available?)
• Arithmetic complexity of first-order definable subsets of recursive Boolean algebras
• Fixed-Point Definability and Polynomial Time

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

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