Theory Seminar - Choiceless Polynomial Time

Choiceless Polynomial Time

Abstract: The “choiceless” computation model of Blass, Gurevich and Shelah (1999, 2002) is an algorithmic framework for computing isomorphism-invariant properties of unordered structures.  Machines in this model lack the ability to make arbitrary choices (such as selecting the “first” neighbor of a vertex in a graph), but have the power of parallel execution over all choices from a set.  In this talk, I will introduce the choiceless model and discuss an intriguing open question:  Is every polynomial-time graph property is computable by a *choiceless* polynomial-time algorithm?  Recent results have demonstrated the surprising power of choiceless algorithms (including fixed-point logic) to solve problems like matching, determinant, linear programming, and isomorphism of Cai-Furer-Immerman graphs.  On the other hand, it can be shown that the dual space V* of a finite vector space V is not constructible in choiceless polynomial-time, though lower bounds for decision problems remain elusive.