arXiv Open Access 2021

Separating Rank Logic from Polynomial Time

Moritz Lichter

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.LO math.LO

Penulis (1)

Moritz Lichter

Format Sitasi

APA MLA BibTeX

Lichter, M. (2021). Separating Rank Logic from Polynomial Time. https://arxiv.org/abs/2104.12999

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2021
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓