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 条
  • [31] Separating Quantum Communication and Approximate Rank
    Anshu, Anurag
    Ben-David, Shalev
    Garg, Ankit
    Jain, Rahul
    Kothari, Robin
    Lee, Troy
    32ND COMPUTATIONAL COMPLEXITY CONFERENCE (CCC 2017), 2017, 79
  • [32] Sutured manifolds and polynomial invariants from higher rank bundles
    Daemi, Aliakbar
    Xie, Yi
    GEOMETRY & TOPOLOGY, 2020, 24 (01) : 49 - 178
  • [33] POLYNOMIAL RANK OF A COMMUTATIVE RING
    COSTA, DL
    COMMUNICATIONS IN ALGEBRA, 1979, 7 (14) : 1509 - 1530
  • [34] The Identity of Rank of Matrix Polynomial
    Wang, Junqing
    Lu, Jiyong
    PROCEEDINGS OF THE THIRD INTERNATIONAL WORKSHOP ON MATRIX ANALYSIS AND APPPLICATIONS, VOL 1, 2009, : 360 - 362
  • [35] POLYNOMIAL BOUND FOR PARTITION RANK IN TERMS OF ANALYTIC RANK
    Milicevic, Luka
    GEOMETRIC AND FUNCTIONAL ANALYSIS, 2019, 29 (05) : 1503 - 1530
  • [36] Polynomial bound for partition rank in terms of analytic rank
    Luka Milićević
    Geometric and Functional Analysis, 2019, 29 : 1503 - 1530
  • [37] ON DIFFERENCES BETWEEN THE BORDER RANK AND THE SMOOTHABLE RANK OF A POLYNOMIAL
    Buczynska, Weronika
    Buczynski, Jaroslaw
    GLASGOW MATHEMATICAL JOURNAL, 2015, 57 (02) : 401 - 413
  • [38] POLYNOMIAL FOLDINGS AND RANK OF TENSORS
    Diaz, Steven P.
    Lutoborski, Adam
    JOURNAL OF COMMUTATIVE ALGEBRA, 2016, 8 (02) : 173 - 206
  • [39] Linear logic and polynomial time (vol 16, pg 947, 2006)
    Mazza, Damiano
    MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2006, 16 (06) : 1165 - 1165
  • [40] BOUNDED LINEAR LOGIC - A MODULAR APPROACH TO POLYNOMIAL-TIME COMPUTABILITY
    GIRARD, JY
    SCEDROV, A
    SCOTT, PJ
    THEORETICAL COMPUTER SCIENCE, 1992, 97 (01) : 1 - 66