skip to content

Choiceless polynomial time

Thursday 8th June 2006 - 11:00 to 12:00
INI Seminar Room 1

We will introduce the choiceless polynomial time (CPT) model of computation, due to Blass, Gurevich and Shelah. With the addition of a counting operator, CPT is known to be more powerful than inflationary fixed-point logic with counting (IFP+C) while still being contained in polynomial time. Blass et al give a number of candidate problems for separating CPT with counting from P, including the query due to Cai, Fuerer and Immerman that separates IFP+C from P. We show that this particular query is definable in CPT, even without counting.

Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons