Separating Rank Logic from Polynomial Time

DOI10.1145/3572918MaRDI QIDQ6366211zbMATH OpenWikidataFDO

Authors

Publication date 27 April 2021

Full work available at URL https://doi.org/10.1145/3572918

Abstract: In the search for a logic capturing polynomial time the most promising candidates are Choiceless Polynomial Time (CPT) and rank logic. Rank logic extends fixed-point logic with counting by a rank operator over prime fields. We show that the isomorphism problem for CFI graphs over $mathbb{Z}_{2^i}$ cannot be defined in rank logic, even if the base graph is totally ordered. However, CPT can define this isomorphism problem. We thereby separate rank logic from CPT and in particular from polynomial time.

This page was built for publication: Separating Rank Logic from Polynomial Time

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