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
- 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
- scientific article; zbMATH DE number 979011 (Why is no real title available?)
- Metafinite model theory
- Relational queries computable in polynomial time
- Structure and complexity of relational queries
Cited in
(31)- Affine systems of equations and counting infinitary logic
- Choiceless polynomial time
- Computation on structures. Behavioural theory, logic, complexity
- Structures computable in polynomial time. I
- Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
- Symbioses between mathematical logic and computer science
- Choiceless polynomial time on structures with small abelian colour classes
- Is polynomial time choiceless?
- 2005 Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '05
- On the Descriptive Complexity of Linear Algebra
- Database Theory, Yuri, and Me
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Choiceless computation and symmetry
- Fixed-Point Definability and Polynomial Time
- On fixed-point logic with counting
- Turing machines with atoms, constraint satisfaction problems, and descriptive complexity
- Characterising choiceless polynomial time with first-order interpretations
- Cellular automata are generic
- Approximations of isomorphism and logics with linear-algebraic operators
- Capturing polynomial time using modular decomposition
- Subspace-invariant \(\mathrm{AC}^0\) formulas
- On the Weisfeiler-Leman dimension of fractional packing
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
- Access structures determined by uniform polymatroids
- On the descriptive complexity of temporal constraint satisfaction problems
- Choiceless polynomial time with witnessed symmetric choice
- Symmetric arithmetic circuits
- Symmetric arithmetic circuits
- The umbilical cord of finite model theory
- Choiceless polynomial time with witnessed symmetric choice
- Can abstract state machines be useful in language theory?
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)
