Fellows Logic Open Seminar

One of the most challenging problems of finite model theory is the question whether there exists a logic capturing polynomial time on arbitrary finite structures. A logic of reference for this problem is fixed-point logic with counting (FPC) which indeed characterizes polynomial time on many interesting classes of structures but, by a famous result due to Cai, Fürer, and Immerman, fails to do so in general. The currently most promising candidates for logics that might actually capture PTIME on all finite structures are on one side extensions of FPC by operators from linear algebra, such as Rank Logic, and on the other side Choiceless Polynomial Time (CPT), introduced by Blass, Gurevich, and Shelah, which will be the topic of this talk. We shall give a precise definition of CPT, and present an equivalent characterization in terms of iterated first-order interpretations. We shall then survey recent results on the expressive power of CPT and discuss some open problems.