Is Polynomial Time Choiceless?

DOI10.1007/978-3-319-23534-9_11zbMath1465.68100OpenAlexW2262891115MaRDI QIDQ2947174

Martin Grohe, Erich Grädel

Publication date: 22 September 2015

Published in: Fields of Logic and Computation II (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-23534-9_11

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (2)

The descriptive complexity of subgraph isomorphism without numerics ⋮ Choiceless Logarithmic Space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite model theory and its applications.
• Affine systems of equations and counting infinitary logic
• Choiceless polynomial time
• An optimal lower bound on the number of variables for graph identification
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Choiceless Polynomial Time on Structures with Small Abelian Colour Classes
• A non-factorial algorithm for canonical numbering of a graph
• Limitations of Algebraic Approaches to Graph Isomorphism Testing
• Choiceless Computation and Symmetry
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
• Characterising Choiceless Polynomial Time with First-Order Interpretations
• On polynomial time computation over unordered structures
• On finite rigid structures
• Classifying the Complexity of Constraints Using Finite Algebras
• Rank logic is dead, long live rank logic!
• Fixed-point definability and polynomial time on graphs with excluded minors
• A Simple Algorithm for Mal'tsev Constraints

This page was built for publication: Is Polynomial Time Choiceless?