On polynomial time computation over unordered structures
From MaRDI portal
Abstract: This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. We show that the examples in a paper of Cai, Furer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another plausible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting.
Recommendations
Cites work
- scientific article; zbMATH DE number 979011 (Why is no real title available?)
- An extension of fixpoint logic with a symmetry-based choice construct
- An optimal lower bound on the number of variables for graph identification
- Choiceless polynomial time
- Equivalence Relations, Invariants, and Normal Forms
- Metafinite model theory
- Relational queries computable in polynomial time
- Structure and complexity of relational queries
Cited in
(27)- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- On the descriptive complexity of temporal constraint satisfaction problems
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Structures computable in polynomial time. I
- Is polynomial time choiceless?
- Characterising choiceless polynomial time with first-order interpretations
- Computation on structures. Behavioural theory, logic, complexity
- Symbioses between mathematical logic and computer science
- Database Theory, Yuri, and Me
- Subspace-invariant \(\mathrm{AC}^0\) formulas
- Can abstract state machines be useful in language theory?
- Choiceless polynomial time
- On fixed-point logic with counting
- On the Descriptive Complexity of Linear Algebra
- Turing machines with atoms, constraint satisfaction problems, and descriptive complexity
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
- On the Weisfeiler-Leman dimension of fractional packing
- Access structures determined by uniform polymatroids
- Choiceless polynomial time with witnessed symmetric choice
- Affine systems of equations and counting infinitary logic
- Capturing polynomial time using modular decomposition
- Cellular automata are generic
- Fixed-Point Definability and Polynomial Time
- Choiceless computation and symmetry
- Approximations of isomorphism and logics with linear-algebraic operators
- Choiceless polynomial time on structures with small abelian colour classes
- 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05
This page was built for publication: On polynomial time computation over unordered structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4779654)
