Descriptive characterizations of computational complexity
type: Item
instance of: scholarly article
title: Descriptive characterizations of computational complexity
zbMATH Open document ID: 0677.68045
DOI: 10.1016/0022-0000(89)90019-6
author: Daniel M. Leivant
published in: Journal of Computer and System Sciences
publication date: 1989-01-01T00:00:00Z
review text: Several complexity classes, such as Nlog-Space, P-Time, P-Space, and Exp- Time are characterized in terms of formulas of the form (\(\forall\) relations) (\(\exists\) objects) \(\phi\) with \(\phi\) quantifier-free. Different syntactic variants of such formulas characterize different complexity classes. In particular, such descriptive characterizations in terms of higher order logical formulas are considered.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4110109
zbMATH Keywords: descriptive complexity
zbMATH Keywords: logical characterization
zbMATH Keywords: of complexity classes
MaRDI profile type: Publication
full work available at URL: 0022-0000(89)90019-6
OpenAlex ID: W2079745007
cites work: Applications of Strict Π11 predicates to infinitary logic
cites work: Q4075450
cites work: The next admissible set
cites work: Henkin quantifiers and complete problems
cites work: Global inductive definability
cites work: Q3220555
cites work: Computable queries for relational data bases
cites work: Q3235339
cites work: Alternation
cites work: Q4058132
cites work: Q3880831
cites work: Q5625130
cites work: On non-determinacy in simple computing devices
cites work: Q5732647
cites work: Q4122837
cites work: A programming language for the inductive sets, and applications
cites work: Number of quantifiers is better than number of tape cells
cites work: Relational queries computable in polynomial time
cites work: Languages that Capture Complexity Classes
cites work: Turing machines and the spectra of first-order formulas
cites work: Metarecursive sets
cites work: Q5573961
cites work: Q3325707
cites work: Second-order and Inductive Definability on Finite Structures
cites work: The polynomial-time hierarchy
cites work: Q5815606
cites work: Finite partially-ordered quantification
description: scientific article; zbMATH DE number 4110109