Separating Rank Logic from Polynomial Time

被引:3
|
作者
Lichter, Moritz [1 ]
机构
[1] Tech Univ Darmstadt, Darmstadt, Germany
来源
2021 36TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS) | 2021年
基金
欧洲研究理事会;
关键词
rank logic; polynomial time; choiceless polynomial time; CFI graphs; NUMBER;
D O I
10.1109/LICS52264.2021.9470598
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 Z(2i) 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.
引用
收藏
页数:13
相关论文
共 50 条
  • [21] Testing Nilpotence of Galois Groups in Polynomial Time
    Arvind, V.
    Kurur, Piyush P.
    ACM TRANSACTIONS ON ALGORITHMS, 2012, 8 (03)
  • [22] Higher type recursion, ramification and polynomial time
    Bellantoni, SJ
    Niggl, KH
    Schwichtenberg, H
    ANNALS OF PURE AND APPLIED LOGIC, 2000, 104 (1-3) : 17 - 30
  • [23] Choiceless Polynomial Time with Witnessed Symmetric Choice
    Lichter, Moritz
    Schweitzer, Pascal
    JOURNAL OF THE ACM, 2024, 71 (02)
  • [24] POLYGRAPHIC PROGRAMS AND POLYNOMIAL-TIME FUNCTIONS
    Bonfante, Guillaume
    Guiraud, Yves
    LOGICAL METHODS IN COMPUTER SCIENCE, 2009, 5 (02)
  • [25] A polynomial time computable metric between point sets
    Ramon, J
    Bruynooghe, M
    ACTA INFORMATICA, 2001, 37 (10) : 765 - 780
  • [26] Polynomial-Time Algorithms for Phylogenetic Inference Problems
    van Iersel, Leo
    Janssen, Remie
    Jones, Mark
    Murakami, Yukihiro
    Zeh, Norbert
    ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018), 2018, 10849 : 37 - 49
  • [27] A system to place observers on a polyhedral terrain in polynomial time
    Marengoni, M
    Draper, BA
    Hanson, A
    Sitaraman, R
    IMAGE AND VISION COMPUTING, 2000, 18 (10) : 773 - 780
  • [28] Constructing composition factors for a linear group in polynomial time
    Holt, Derek
    Leedham-Green, C. R.
    O'Brien, E. A.
    JOURNAL OF ALGEBRA, 2020, 561 : 215 - 236
  • [29] Polynomial-Time Solvability of the Maximum Clique Problem
    Tomita, Etsuji
    Nakanishi, Hiroaki
    COMPUTING AND COMPUTATIONAL INTELLIGENCE, PROCEEDINGS, 2009, : 203 - +
  • [30] A polynomial time computable metric between point sets
    Jan Ramon
    Maurice Bruynooghe
    Acta Informatica, 2001, 37 : 765 - 780