|
One Step Closer to P
Sophie Koffler
UMASS
Abstract: In finite model theory, a key line of research is the quest for a logical language that expresses exactly the set of (order-independent) properties computable in polynomial time. In this talk we will present two different logics which are current candidates for capturing P: Rank Logic and Choiceless Polynomial Time (CPT). In a previous talk, Fixed Point Logic with Counting (FPC) was introduced and shown not to capture P through its inability to express the CFI property. In this talk I will explain how the two current candidate logics describe the CFI property. This will demonstrate how they take us one step closer to capturing P.