Separating Rank Logic from Polynomial Time

Understand

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.