Is polynomial time choiceless?

DOI10.1007/978-3-319-23534-9_11MaRDI QIDQ2947174zbMATH OpenOpenAlexFDO

Authors Erich Grädel, Martin Grohe

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)

Recommendations

• Choiceless polynomial time
• scientific article; zbMATH DE number 1670468
• Is there a logic for polynomial time?
• On polynomial time computation over unordered structures
• scientific article; zbMATH DE number 1670472

Cites work

• A non-factorial algorithm for canonical numbering of a graph
• A Simple Algorithm for Mal'tsev Constraints
• Affine systems of equations and counting infinitary logic
• An optimal lower bound on the number of variables for graph identification
• Characterising choiceless polynomial time with first-order interpretations
• Choiceless computation and symmetry
• Choiceless polynomial time
• Choiceless polynomial time on structures with small abelian colour classes
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Classifying the Complexity of Constraints Using Finite Algebras
• Finite model theory and its applications.
• Fixed-point definability and polynomial time on graphs with excluded minors
• scientific article; zbMATH DE number 6691390 (Why is no real title available?)
• scientific article; zbMATH DE number 515737 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• Limitations of algebraic approaches to graph isomorphism testing
• On finite rigid structures
• On polynomial time computation over unordered structures
• On the Structure of Polynomial Time Reducibility
• Rank logic is dead, long live rank logic!
• Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

Cited in

(13)

• scientific article; zbMATH DE number 1670468 (Why is no real title available?)
• scientific article; zbMATH DE number 1670472 (Why is no real title available?)
• Choiceless polynomial time on structures with small abelian colour classes
• A logic for PTIME and a parameterized halting problem
• Is there a logic for polynomial time?
• Characterising choiceless polynomial time with first-order interpretations
• On polynomial time computation over unordered structures
• Choiceless Logarithmic Space
• Choiceless polynomial time with witnessed symmetric choice
• Choiceless computation and symmetry: limitations of definability
• Choiceless polynomial time with witnessed symmetric choice
• Separating rank logic from polynomial time
• Symmetric proofs in the ideal proof system

This page was built for publication: Is polynomial time choiceless?

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