scientific article; zbMATH DE number 1086669

MaRDI QIDQ4362919zbMATH OpenFDO

Authors H. Imhof

Publication date 13 August 1998

zbMATH Keywords

arity hierarchiescollapsecomplexity classescomplexity levelsfinite ordered structuresleast fixed point logicpartial fixed point logicsecond order logictransitive closure logic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
• Languages that Capture Complexity Classes
• Context-sensitive transitive closure operators
• Proper hierarchies in polylogarithmic time and absence of complete problems
• Arithmetic theories for computational complexity problems
• scientific article; zbMATH DE number 223336
• Expressing versus proving: relating forms of complexity in logic
• Many Facets of Complexity in Logic
• scientific article; zbMATH DE number 4130360
• Generalized Quantifiers and Logical Reducibilities

Cited in

(4)

• scientific article; zbMATH DE number 4174914 (Why is no real title available?)
• Arithmetic theories for computational complexity problems
• SEPARATING AUXILIARY ARITY HIERARCHY OF FIRST-ORDER INCREMENTAL EVALUATION SYSTEMS USING (3K+1)-ary INPUT RELATIONS
• A hierarchical approach to computer Hex

This page was built for publication:

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