Choiceless computation and symmetry


Conference Paper

Many natural problems in computer science concern structures like graphs where elements are not inherently ordered. In contrast, Turing machines and other common models of computation operate on strings. While graphs may be encoded as strings (via an adjacency matrix), the encoding imposes a linear order on vertices. This enables a Turing machine operating on encodings of graphs to choose an arbitrary element from any nonempty set of vertices at low cost (the Augmenting Paths algorithm for Bipartite Matching being an example of the power of choice). However, the outcome of a computation is liable to depend on the external linear order (i.e., the choice of encoding). Moreover, isomorphism-invariance/encoding-independence is an undecidable property of Turing machines. This trouble with encodings led Blass, Gurevich and Shelah [3] to propose a model of computation known as BGS machines that operate directly on structures. BGS machines preserve symmetry at every step in a computation, sacrificing the ability to make arbitrary choices between indistinguishable elements of the input structure (hence "choiceless computation"). Blass et al. also introduced a complexity class CPT+C (Choiceless Polynomial Time with Counting) defined in terms of polynomially bounded BGS machines. While every property finite structures in CPT+C is polynomial-time computable in the usual sense, it is open whether conversely every isomorphism-invariant property in P belongs to CPT+C. In this paper we give evidence that CPT+C P by proving the separation of the corresponding classes of function problems. Specifically, we show that there is an isomorphism-invariant polynomial-time computable function problem on finite vector spaces ("given a finite vector space V, output the set of hyperplanes in V") that is not computable by any CPT+C program. In addition, we give a new simplified proof of the Support Theorem, which is a key step in the result of [3] that a weak version of CPT+C absent counting cannot decide the parity of sets. © 2010 Springer-Verlag Berlin Heidelberg.

Full Text

Duke Authors

Cited Authors

  • Rossman, B

Published Date

  • September 20, 2010

Published In

Volume / Issue

  • 6300 LNCS /

Start / End Page

  • 565 - 580

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3642150241

International Standard Book Number 13 (ISBN-13)

  • 9783642150241

Digital Object Identifier (DOI)

  • 10.1007/978-3-642-15025-8_28

Citation Source

  • Scopus