### Choiceless Polynomial Time

by Blass and Gurevich and Shelah. [BGSh:533]

Annals Pure and Applied Logic, 1999

Turing machines define polynomial time (PTime) on strings but
cannot deal with structures like graphs directly, and there is
no
known, easily computable string encoding of isomorphism classes
of
structures. Is there a computation model whose machines do not
distinguish between isomorphic structures and compute exactly
PTime
properties? This question can be recast as follows: Does there
exist a
logic that captures polynomial time (without presuming the presence
of
a linear order)? Earlier, one of us conjectured the negative
answer. The problem motivated a quest for stronger and stronger PTime
logics. All these logics avoid arbitrary choice. Here we attempt to
capture the choiceless fragment of PTime. Our computation model is a
version of abstract state machines (formerly called evolving
algebras). The idea is to replace arbitrary choice with parallel
execution. The resulting logic is more expressive than other PTime
logics in the literature. A more difficult theorem shows that the
logic does not capture all PTime.

Back to the list of publications