A generalized quantifier concept in computational complexity theory

DOI10.1007/3-540-46583-9_5MaRDI QIDQ4955353zbMATH OpenFDO

Authors Heribert Vollmer

Publication date 8 May 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46583-9_5

zbMATH Keywords

circuits with monoidal gatescomputational complexity theorydescriptive complexitygeneralized quantifierleaf language definabilityLindström quantifiersoracle separationstype 2 operators

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19)

Review text

In finite model theory, examinations of the expressive power of various logics enhanced by Lindström and other quantifiers form a very well established field of active research. Descriptive complexity theory has characterized a great bulk of complexity classes by such logics. In this paper, a notion of generalized quantifier in computational complexity theory is explored and used to give a unified treatment of leaf language definability, oracle separations, type 2 operators, and circuits with monoidal gates. Relations to Lindström quantifiers are pointed out. For the entire collection see [Zbl 0931.00026].

Recommendations

• scientific article; zbMATH DE number 3845566
• scientific article; zbMATH DE number 4075030
• The quantifier complexity of NF
• Toward a generalized computability theory
• scientific article; zbMATH DE number 4033724
• scientific article; zbMATH DE number 3873306
• Universal quantifiers and time complexity of random access machines
• Complexity classes defined by counting quantifiers
• Qualitative relativizations of complexity classes
• Complexity of generalized satisfiability counting problems

Cited in

(24)

• Relating polynomial time to constant depth
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• Quantum circuits with classical channels and the principle of deferred measurements
• Explicit exponential lower bounds for exact hyperplane covers
• Capturing relativized complexity classes with Lindström quantifiers
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Computational complexity and the expressive power of logics
• scientific article; zbMATH DE number 1043779 (Why is no real title available?)
• scientific article; zbMATH DE number 1163938 (Why is no real title available?)
• Generalized Quantifiers and Logical Reducibilities
• scientific article; zbMATH DE number 1421069 (Why is no real title available?)
• Size, cost and capacity: a semantic technique for hard random QBFs
• Approximation in (Poly-) Logarithmic Space
• The power word problem
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Capturing complexity classes with Lindström quantifiers
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Lindström quantifiers and leaf language definability
• Knapsack in hyperbolic groups
• Parallel algorithms for power circuits and the word problem of the Baumslag group
• Enumeration classes defined by circuits
• The complexity of circumscriptive inference in Post's lattice
• On the quantifier complexity of \(\Delta_{n+1}(T)\)-induction
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems

This page was built for publication: A generalized quantifier concept in computational complexity theory

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