Characterising choiceless polynomial time with first-order interpretations

DOI10.1109/LICS.2015.68MaRDI QIDQ4635846zbMATH OpenFDO

Authors Erich Grädel, Wied Pakusa, Svenja Schalthöfer, Łukasz Kaiser

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/LICS.2015.68

Mathematics Subject Classification ID

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

Recommendations

• Choiceless polynomial time
• On polynomial time computation over unordered structures
• scientific article; zbMATH DE number 1670472
• Is polynomial time choiceless?
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs

Cited in

(11)

• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• scientific article; zbMATH DE number 1670472 (Why is no real title available?)
• Is polynomial time choiceless?
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Choiceless Logarithmic Space
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• A Characterization of Alternating Log Time by First Order Functional Programs
• Addendum to ``Choiceless polynomial time
• Choiceless polynomial time with witnessed symmetric choice
• Choiceless computation and symmetry: limitations of definability
• Choiceless polynomial time with witnessed symmetric choice

This page was built for publication: Characterising choiceless polynomial time with first-order interpretations

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