Choiceless Polynomial Time

Choiceless Polynomial Time - Ben Rossman

Ben Rossman
University of Toronto
October 14, 2019

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 have the power of parallel execution, but lack the ability to make arbitrary choices.  For example, a choiceless algorithm cannot freely select an arbitrary neighbor of a vertex in an unordered graph, but may execute a subroutine in parallel over all neighbors.  In this talk, I will give an overview of results in the choiceless model and discuss the intriguing open question:  Does every graph property that is decidable by a poly-time Turing machine admit a choiceless poly-time algorithm?