From quantifier depth to quantifier number: separating structures with k variables
From MaRDI portal
From quantifier depth to quantifier number: separating structures with \(k\) variables
Cites work
- An n! lower bound on formula size
- An application of games to the completeness problem for formalized theories
- An optimal lower bound on the number of variables for graph identification
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Elements of finite model theory.
- Equivalence in finite-variable logics is complete for polynomial time
- Finite Variable Logics in Descriptive Complexity Theory
- Hard examples for the bounded depth Frege proof system
- scientific article; zbMATH DE number 1754602 (Why is no real title available?)
- Limitations of algebraic approaches to graph isomorphism testing
- Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
- Many hard examples for resolution
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Near optimal seperation of tree-like and general resolution
- Near-optimal lower bounds on quantifier depth and Weisfeiler-Leman refinement steps
- Number of quantifiers is better than number of tape cells
- On the complexity of existential positive queries
- On the number of quantifiers as a complexity measure
- Short proofs are narrow—resolution made simple
- Size space tradeoffs for resolution
- Succinctness of Order-Invariant Logics on Depth-Bounded Structures
- The complexity of resolution refinements
- The iteration number of the Weisfeiler-Leman algorithm
- The succinctness of first-order logic on linear orders
- The Succinctness of First-order Logic over Modal Logic via a Formula Size Game
- Upper and lower bounds for first order expressibility
This page was built for publication: From quantifier depth to quantifier number: separating structures with \(k\) variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6970199)
