Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
Publication
, Journal Article
Dawar, A; Richerby, D; Rossman, B
Published in: Annals of Pure and Applied Logic
March 1, 2008
We consider Choiceless Polynomial Time (over(C, ̃) PT), a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, Fürer and Immerman to separate fixed-point logic with counting (IFP + C) from P. This settles a question posed by Blass et al. The program we present uses sets of unbounded finite rank: we demonstrate that this is necessary by showing that the query cannot be computed by any program that has a constant bound on the rank of sets used, even in over(C, ̃) PT(Card), an extension of over(C, ̃) PT with counting. © 2007 Elsevier B.V. All rights reserved.
Duke Scholars
Published In
Annals of Pure and Applied Logic
DOI
ISSN
0168-0072
Publication Date
March 1, 2008
Volume
152
Issue
1-3
Start / End Page
31 / 50
Related Subject Headings
- General Mathematics
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics
Citation
APA
Chicago
ICMJE
MLA
NLM
Dawar, A., Richerby, D., & Rossman, B. (2008). Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. Annals of Pure and Applied Logic, 152(1–3), 31–50. https://doi.org/10.1016/j.apal.2007.11.011
Dawar, A., D. Richerby, and B. Rossman. “Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs.” Annals of Pure and Applied Logic 152, no. 1–3 (March 1, 2008): 31–50. https://doi.org/10.1016/j.apal.2007.11.011.
Dawar A, Richerby D, Rossman B. Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. Annals of Pure and Applied Logic. 2008 Mar 1;152(1–3):31–50.
Dawar, A., et al. “Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs.” Annals of Pure and Applied Logic, vol. 152, no. 1–3, Mar. 2008, pp. 31–50. Scopus, doi:10.1016/j.apal.2007.11.011.
Dawar A, Richerby D, Rossman B. Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. Annals of Pure and Applied Logic. 2008 Mar 1;152(1–3):31–50.
Published In
Annals of Pure and Applied Logic
DOI
ISSN
0168-0072
Publication Date
March 1, 2008
Volume
152
Issue
1-3
Start / End Page
31 / 50
Related Subject Headings
- General Mathematics
- 0802 Computation Theory and Mathematics
- 0101 Pure Mathematics