Choiceless Polynomial Time on Structures with Small Abelian Colour Classes

DOI10.1007/978-3-662-44522-8_5zbMath1426.68106OpenAlexW157368094MaRDI QIDQ2922002

Wied Pakusa, Unnamed Author, Erich Grädel, Martin Grohe

Publication date: 14 October 2014

Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-44522-8_5

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items

Is Polynomial Time Choiceless? ⋮ RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC! ⋮ Benchmark Graphs for Practical Graph Isomorphism ⋮ Choiceless Logarithmic Space

Cites Work

• Unnamed Item
• Unnamed Item
• Finite model theory and its applications.
• Affine systems of equations and counting infinitary logic
• Choiceless polynomial time
• Isomorphism of graphs of bounded valence can be tested in 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
• Definability of linear equation systems over groups and rings
• Choiceless Computation and Symmetry
• On polynomial time computation over unordered structures
• Maximum Matching and Linear Programming in Fixed-Point Logic with Counting
• Fixed-point definability and polynomial time on graphs with excluded minors