Prefer a chat interface with context about you and your work?
Separating Rank Logic from Polynomial Time
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 …