Paper Info
Title
The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
Abstract
In Descriptive Complexity, we investigate the use of logics to characterize computational complexity classes. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the first result in this area, other relations between logics and complexity classes have been established. Well-known results usually involve first-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the first-order logic extended by the least fixed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this paper, we will analyze the combined use of higher-order logics of order i, HO^i, for i=2, extended by the least fixed-point operator, and we will prove that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HO^i(LFP), for i=2, does not collapse, that is, HO^i(LFP)@?HO^i^+^1(LFP).
Year
DOI
Venue
2011
10.1016/j.entcs.2011.03.006
Electr. Notes Theor. Comput. Sci.
Keywords
Field
DocType
fixed-point operator,second-order logic,higher-order logics,class pspace,deterministic exponential time hierarchy,complexity class,computational complexity class,class np,existential second-order logic,higher-order logic,class p,first-order logic,descriptive complexity,transitive closure,first order logic,polynomial time,fixed point,second order,higher order logic,computational complexity
Quantum complexity theory,Complexity class,PH,Discrete mathematics,Structural complexity theory,EXPTIME,Computer science,P,Descriptive complexity theory,Transitive closure
Journal
Volume
ISSN
Citations 
269,
Electronic Notes in Theoretical Computer Science
0
PageRank 
References 
Authors
0.34
8
2
Name
Order
Citations
PageRank
Cibele Matos Freire111.36
Ana Teresa Martins224.80