Arithmetical definability and computational complexity
type: Item
instance of: scholarly article
title: Arithmetical definability and computational complexity
zbMATH Open document ID: 1070.68047
author: Yassine Hachaïchi
published in: Theoretical Computer Science
publication date: 2004-10-27T00:00:00Z
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 03C13
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 2111107
zbMATH Keywords: Descriptive complexity
zbMATH Keywords: Bounded arithmetic
zbMATH Keywords: Logic and complexity
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.03.027
OpenAlex ID: W2171255643
cites work: On uniformity within \(NC^ 1\)
cites work: Q5691140
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Q3800030
cites work: Q4850061
cites work: Decision Problems of Finite Automata Design and Related Arithmetics
cites work: Rudimentary relations and primitive recursion: A toolbox
cites work: A spectrum hierarchy
cites work: Capturing complexity classes by fragments of second-order logic
cites work: A descriptive complexity approach to the linear hierarchy.
cites work: Q5286672
cites work: Languages that Capture Complexity Classes
cites work: Q4227581
cites work: An arithmetical characterization of NP
cites work: A normal form for arithmetical representation of \({\mathcal N}{\mathcal P}\)-sets
cites work: Complexity classes and theories of finite models
cites work: Rudimentary Languages and Second‐Order Logic
cites work: Q4298260
cites work: Theory of Formal Systems. (AM-47)
cites work: The polynomial-time hierarchy
cites work: Q5723184
cites work: Rudimentary Predicates and Relative Computation
cites work: Notes on polynomially bounded arithmetic
DOI: 10.1016/J.TCS.2004.03.027
description: scientific article; zbMATH DE number 2111107