November 14, 2017 Theory Seminar 4:00 pm, CS 140

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.