Choiceless Polynomial Time, Counting and
Anuj Dawar, David Richerby, Benjamin Rossman · 2007
We consider Choiceless Polynomial Time (e CPT), a language introduced by Blass, Gurevich and Shelah, and show that it can express a query originally constructed by Cai, F urer and Immerman to separate xed-p oint logic with counting (IFP + C) from P. This settles a question posed by Blass et al. The program we present uses sets of unbounded nite 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 e CPT(Card), an extension of e CPT with counting.