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 条

[41] Light affine lambda calculus and polynomial time strong normalization
Terui, Kazushige
ARCHIVE FOR MATHEMATICAL LOGIC, 2007, 46 (3-4) : 253 - 280
[42] Exponential Time Complexity of the Permanent and the Tutte Polynomial (Extended Abstract)
Dell, Holger
Husfeldt, Thore
Wahlen, Martin
AUTOMATA, LANGUAGES AND PROGRAMMING, PT I, 2010, 6198 : 426 - +
[43] Conjectured polynomial time primality tests for numbers of special forms
Terzic, Predrag
NOTES ON NUMBER THEORY AND DISCRETE MATHEMATICS, 2014, 20 (05) : 40 - 43
[44] Polynomial time solvability of non-symmetric semidefinite programming
Hu, Sheng-Long
Huang, Zheng-Hai
OPERATIONS RESEARCH LETTERS, 2010, 38 (05) : 358 - 360
[45] Learning Two Layer Rectified Neural Networks in Polynomial Time
Bakshi, Ainesh
Jayaram, Rajesh
Woodruff, David P.
CONFERENCE ON LEARNING THEORY, VOL 99, 2019, 99
[46] Polynomial-time Algorithm for Distributed Server Allocation Problem
Sawa, Takaaki
He, Fujun
Kawabata, Akio
Oki, Eiji
PROCEEDING OF THE 2019 IEEE 8TH INTERNATIONAL CONFERENCE ON CLOUD NETWORKING (CLOUDNET), 2019,
[47] On polynomial zero exclusion from an RHP sector
Casagrande, Daniele
Krajewski, Wieslaw
Viaro, Umberto
2018 23RD INTERNATIONAL CONFERENCE ON METHODS & MODELS IN AUTOMATION & ROBOTICS (MMAR), 2018, : 648 - 653
[48] A polynomial time primal network simplex algorithm for minimum cost flows
Orlin, JB
MATHEMATICAL PROGRAMMING, 1997, 78 (02) : 109 - 129
[49] Oracle-polynomial-time approximation of largest simplices in convex bodies
Brieden, A
Gritzmann, P
Klee, V
DISCRETE MATHEMATICS, 2000, 221 (1-3) : 79 - 92
[50] A Polynomial-Time Algorithm for the Planar Quantified Integer Programming Problem
Liang, Zhiyao
Subramani, K.
KNOWLEDGE ENGINEERING AND MANAGEMENT, 2011, 123 : 201 - +

← 1 2 3 4 5 →