scientific article; zbMATH DE number 1453080

MaRDI QIDQ4955353zbMATH OpenFDO

Authors Heribert Vollmer

Publication date 8 May 2001

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)

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:

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