Choiceless polynomial time

Details Choiceless polynomial time Choiceless polynomial time

1997-05-15

arxiv.org/abs/math/9705225v1

Mathematics

Logic

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Choiceless polynomial time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Choiceless polynomial time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Choiceless polynomial time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-318453