Skip to content

LAA

Seminar

Choiceless polynomial time

Richerby, D (Athens)
Thursday 08 June 2006, 11:00-12:00

Seminar Room 1, Newton Institute

Abstract

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.

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧