Title | ||
---|---|---|
Choiceless Polynomial Time, Counting and the Cai-Fürer-Immerman Graphs: (Extended Abstract) |
Abstract | ||
---|---|---|
We consider Choiceless Polynomial Time (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 C˜PT(Card), an extension of C˜PT with counting. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1016/j.entcs.2005.05.024 | Electronic Notes in Theoretical Computer Science |
Keywords | DocType | Volume |
Descriptive complexity,finite model theory,counting,choiceless polynomial time | Journal | 143 |
ISSN | Citations | PageRank |
1571-0661 | 3 | 0.41 |
References | Authors | |
5 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
anuj dawar | 1 | 883 | 77.18 |
David M. Richerby | 2 | 142 | 14.06 |
Benjamin Rossman | 3 | 298 | 20.00 |