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 条
  • [1] Separating Rank Logic from Polynomial Time
    Lichter, Moritz
    JOURNAL OF THE ACM, 2023, 70 (02)
  • [2] Separating Polynomial χ-Boundedness from χ-Boundedness
    Brianski, Marcin
    Davies, James
    Walczak, Bartosz
    COMBINATORICA, 2024, 44 (01) : 1 - 8
  • [3] Soft linear logic and polynomial time
    Lafont, Y
    THEORETICAL COMPUTER SCIENCE, 2004, 318 (1-2) : 163 - 180
  • [4] Separating Graph Logic from MSO
    Antonopoulos, Timos
    Dawar, Anuj
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES, PROCEEDINGS, 2009, 5504 : 63 - 77
  • [5] Polynomial-Time Random Oracles and Separating Complexity Classes
    Hitchcock, John M.
    Sekoni, Adewale
    Shafei, Hadi
    ACM TRANSACTIONS ON COMPUTATION THEORY, 2021, 13 (01)
  • [6] A FRAGMENT OF DEPENDENCE LOGIC CAPTURING POLYNOMIAL TIME
    Ebbing, Johannes
    Kontinen, Juha
    Mueller, Julian-Steffen
    Vollmer, Heribert
    LOGICAL METHODS IN COMPUTER SCIENCE, 2014, 10 (03)
  • [7] Polynomial time in untyped elementary linear logic
    Laurent, Olivier
    THEORETICAL COMPUTER SCIENCE, 2020, 813 : 117 - 142
  • [8] Polynomial-time learning in logic programming and constraint logic programming
    Sebag, M
    Rouveirol, C
    INDUCTIVE LOGIC PROGRAMMING, 1997, 1314 : 105 - 126
  • [9] Polynomial-time learnability of logic programs with local variables from entailment
    Rao, MRKK
    Sattar, A
    THEORETICAL COMPUTER SCIENCE, 2001, 268 (02) : 179 - 198
  • [10] On separating constant from polynomial ambiguity of finite automata
    Kupke, J
    SOFSEM 2006: THEORY AND PRACTICE OF COMPUTER SCIENCE, PROCEEDINGS, 2006, 3831 : 379 - 388