Choiceless Polynomial Time on Structures with Small Abelian Colour Classes

DOI10.1007/978-3-662-44522-8_5zbMATH Open1426.68106OpenAlexW157368094MaRDI QIDQ2922002FDOQ2922002

Wied Pakusa, Faried Abu Zaid, 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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Fixed-point definability and polynomial time on graphs with excluded minors
• An optimal lower bound on the number of variables for graph identification
• Finite model theory and its applications.
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Affine systems of equations and counting infinitary logic
• Choiceless polynomial time
• On polynomial time computation over unordered structures
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Maximum Matching and Linear Programming in Fixed-Point Logic with Counting
• Definability of linear equation systems over groups and rings
• Choiceless Computation and Symmetry

Cited In (5)

• RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC!
• Is Polynomial Time Choiceless?
• Choiceless Logarithmic Space
• Choiceless polynomial time with witnessed symmetric choice
• Benchmark Graphs for Practical Graph Isomorphism

This page was built for publication: Choiceless Polynomial Time on Structures with Small Abelian Colour Classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922002)