Is Polynomial Time Choiceless?
Is Polynomial Time Choiceless?
复制标题
多项式时间是无选择的吗？
DOI：
10.1007/978-3-319-23534-9_11
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Grohe
中科院分区：
文献类型：
--
作者：
E. Grädel;M. Grohe
A long time ago, Yuri Gurevich made precise the problem of whether there is a logic capturing polynomial-time on arbitrary finite structures, and conjectured that no such logic exists. This conjecture is still open. Nevertheless, together with Andreas Blass and Saharon Shelah, he has also proposed what still seems to be the most promising candidate for a logic for polynomial time, namely Choiceless Polynomial Time (with counting). We survey some recent results on this logic.
登录
查看更多内容
DOI：
10.1007/978-3-662-44522-8_5
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
Faried Abu Zaid;E. Grädel;Martin Grohe;Wied Pakusa
通讯作者：
Wied Pakusa
无选择多项式时间的强扩展公理和 Shelah 零一定律
影响因子：
0.6
作者：
A. Blass;Y. Gurevich
通讯作者：
Y. Gurevich
DOI：
--
发表时间：
2001
期刊：
Journal of Symbolic Logic (JSL)
影响因子：
--
作者：
A. Blass;Y. Gurevich;S. Shelah
通讯作者：
S. Shelah
无选择计算和对称性
DOI：
--
发表时间：
2010
期刊：
Fields of Logic and Computation
影响因子：
--
作者：
Benjamin Rossman
通讯作者：
Benjamin Rossman
作为复杂性衡量标准的表达性：结果和方向
DOI：
10.1109/psct.1987.10319271
发表时间：
1987
期刊：
Proceeding Structure in Complexity Theory
影响因子：
--
作者：
N. Immerman
通讯作者：
N. Immerman