Arithmetical definability and computational complexity

DOI10.1016/J.TCS.2004.03.027zbMATH Open1070.68047OpenAlexW2171255643MaRDI QIDQ1885035FDOQ1885035

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

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

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

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

Cited In (11)

• Arithmetic definability by formulas with two quantifiers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Arithmetic complexity of first-order definable subsets of recursive Boolean algebras
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Many Facets of Complexity in Logic
• Title not available (Why is that?)
• 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)