Choiceless polynomial time (Q1125059)

Problems in combinatorics, database theory, etc., whose computational complexity we want to examine, are mostly naturally defined as sets of structures (graphs, relations, etc.). In order to use machine models, as, e.g., Turing machines for this study, one has to encode structures as strings. This, however, leads to the problem that there is no known, easily computable encoding that does not distinguish between isomorphic structures. The authors examine the question if there is a computation model that operates directly on structures and that captures the class PTime (polynomial time) over structures. The model introduced here (a form of abstract state machines) is as powerful as any other model introduced in the literature for the same purpose (for example relational machines, see, e.g., \textit{S. Abiteboul, C. H. Papadimitriou} and \textit{V. Vianu}, ``Reflective relational machines'' [Inf. Comput. 143, No. 2, 110-136 (1998; Zbl 0918.68017)]; \textit{S. Abiteboul, M. Y. Vardi} and \textit{V. Vianu}, ``Fixpoint logics, relational machines, and computational complexity'' [J. ACM 44, No. 1, 30-56 (1997; Zbl 0883.68070)]); it even appears to be more powerful. Nevertheless, it is shown that it does not capture all of PTime (examples for problems in the difference are parity and bipartite matching). The captured fragment of PTime is called choiceless polynomial time, because it is shown that it corresponds to polynomial time where arbitrary choices (i.e., pseudo-code statements of the form ``choose an arbitrary \(y\in Y\)'') are eliminated by means of parallel execution. This of course only has a real effect for problems where the resource bound prevents the computation from trying all possible choices. Some extensions of choiceless polynomial time (that again do not capture all of PTime) are examined.