DIMACS TR: 97-20
Choiceless polynomial time
Authors: Andreas Blass, Yuri Gurevich and Saharon Shelah
ABSTRACT
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 of 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.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-20.ps.gz
DIMACS Home Page