Choiceless Polynomial Time

Citation: Andreas Blass, Yuri Gurevich, and Saharon Shelah, "Choiceless Polynomial Time", Annals of Pure and Applied Logic 100 (1999), 141-187.
Summary: ASMs are used to describe the choiceless fragment of polynomial time using structures rather than strings as input.
Subjects: Logic & Computability
Download: PostScript, PDF, Compressed PostScript
Notes: See also the zero-one law proved for this model of computation, as well as a consideration of unordered structures.