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, 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 \(\ne\) 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Blass, A., Gurevich, Y.: Strong extension axioms and Shelah’s zero-one law for choiceless polynomial time. Journal of Symbolic Logic 68(1), 65–131 (2003)
Blass, A., Gurevich, Y.: A quick update on the open problems in Blass-Gurevich-Shelah’s article, On polynomial time computations over unordered structures (Decembmer 2005), http://research.microsoft.com/en-us/um/people/gurevich/Opera/150a.pdf
Blass, A., Gurevich, Y., Shelah, S.: Choiceless polynomial time. Annals of Pure and Applied Logic 100(1-3), 141–187 (1999)
Blass, A., Gurevich, Y., Shelah, S.: On polynomial time computation over unordered structures. Journal of Symbolic Logic 67(3), 1093–1125 (2002)
Cai, J.-Y., Fürer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), 389–410 (1992)
Chandra, A., Harel, D.: Structure and complexity of relational queries. Journal of Computer and System Sciences 25, 99–128 (1982)
Dawar, A., Richerby, D., Rossman, B.: Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. Annals of Pure and Applied Logic 152, 31–50 (2008)
Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R.M. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol. 7, pp. 43–73 (1974)
Gurevich, Y.: Toward logic tailored for computational complexity. In: Richter, M.M., et al. (eds.) Computation and Proof Theory. Springer Lecture Notes in Mathematics, pp. 175–216. Springer, Heidelberg (1984)
Immerman, N.: Relational queries computable in polynomial time. Information and Control 68(1-3), 86–104 (1986)
Shelah, S.: Choiceless polynominal time logic: Inability to express. In: Clote, P.G., Schwichtenberg, H. (eds.) CSL 2000. LNCS, vol. 1862, pp. 72–125. Springer, Heidelberg (2000)
Vardi, M.Y.: The complexity of relational query languages. In: Proc. 14th ACM Symp. on Theory of Computing, pp. 137–146 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Rossman, B. (2010). Choiceless Computation and Symmetry. In: Blass, A., Dershowitz, N., Reisig, W. (eds) Fields of Logic and Computation. Lecture Notes in Computer Science, vol 6300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15025-8_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-15025-8_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15024-1
Online ISBN: 978-3-642-15025-8
eBook Packages: Computer ScienceComputer Science (R0)