Math @ Duke

Publications [#348690] of Benjamin Rossman
Papers Published
 Rossman, B, Choiceless computation and symmetry,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6300 LNCS
(September, 2010),
pp. 565580, ISBN 3642150241 [doi]
(last updated on 2022/05/19)
Abstract: 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, isomorphisminvariance/encodingindependence 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 polynomialtime computable in the usual sense, it is open whether conversely every isomorphisminvariant 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 isomorphisminvariant polynomialtime 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 SpringerVerlag Berlin Heidelberg.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

