Strong extension axioms and Shelah’s zero-one law for choiceless polynomial time. (English) Zbl 1045.03039
This article explores the stochastic behavior of the choiceless polynomial time machine (or BGS model of computation) introduced by A. Blass, Y. Gurevich and S. Shelah [Ann. Pure Appl. Logic 100, 141–187 (1999; Zbl 0936.03037)]. Much of the article is devoted to an exposition of a result of Shelah [S. Shelah, “Choiceless polynomial time logic: inability to express”, Lect. Notes Comput. Sci. 1862, 72–125 (2000; Zbl 0973.03055)]: if there is a BGS program \(\Pi\) and two classes of structures \(\mathcal K_0\) and \(\mathcal K_1\) such that: (i) the program \(\Pi\) halts on all inputs from \(\mathcal K_0 \cup \mathcal K_1\), and (ii) the program \(\Pi\) outputs TRUE for any input from \(\mathcal K_1\) and FALSE for any input from \(\mathcal K_0\), then at least one of \(\mathcal K_0\), \(\mathcal K_1\) has asymptotic probability zero. The paper is self-contained and accessible, if technically complex. The first fourth of the paper is devoted to a description of the BGS model and some of its properties. Here are some highlights.
The paper introduces a generalization of the notion of a random structure of a given signature. It starts with a notion of a {signum}, a generalization of the notion of a relation, and then introduces random graphs, random digraphs, random tournaments, etc., as examples of random signa. Signa are designed for ready application of extension axioms, and the results of this paper actually apply to random signa.
It reviews the BGS model of computation, which (very roughly) starts with an input structure of domain \(I\), generates the hereditarily finite subsets HF\((I)\) of \(I\), on which a BGS program defines certain set-theoretic steps for a computation. The number of steps used for a computation is a time bound, while the number of elements of HF\((I)\) “activated” is used as a space bound. The BGS model is able to carry out certain parallel computations.
It is readily shown that there are BGS-computable queries that cannot be fixed by standard extension axioms. Thus they use {strong} extension axioms, which assert not only the existence of vertices satisfying certain diagrammatic properties, but in fact that a certain proportion of all vertices satisfy these properties. It turns out that that all BGS-computable queries are fixed by strong extension properties.
Although the BGS model is able to do arithmetic, it is unable to compute unbounded cardinalities withing a fixed number of steps. The remainder of the paper is devoted to a proof of a stronger result from Shelah [loc. cit.]: Let \(\Pi\) be a BGS program (producing a Boolean output) such that for any input, there is a polynomial bound on the number of active elements. Then there exists a class \(\mathcal C\) of signa (of asymptotic probability 1), a Boolean value \(v\) and an integer \(m\) such that for each input from \(\mathcal C\), either \(\Pi\) halts in precisely \(m\) steps and outputs \(v\) or it doesn’t halt at all. The proof relies on extensive dissection of BGS computations.
The paper introduces a generalization of the notion of a random structure of a given signature. It starts with a notion of a {signum}, a generalization of the notion of a relation, and then introduces random graphs, random digraphs, random tournaments, etc., as examples of random signa. Signa are designed for ready application of extension axioms, and the results of this paper actually apply to random signa.
It reviews the BGS model of computation, which (very roughly) starts with an input structure of domain \(I\), generates the hereditarily finite subsets HF\((I)\) of \(I\), on which a BGS program defines certain set-theoretic steps for a computation. The number of steps used for a computation is a time bound, while the number of elements of HF\((I)\) “activated” is used as a space bound. The BGS model is able to carry out certain parallel computations.
It is readily shown that there are BGS-computable queries that cannot be fixed by standard extension axioms. Thus they use {strong} extension axioms, which assert not only the existence of vertices satisfying certain diagrammatic properties, but in fact that a certain proportion of all vertices satisfy these properties. It turns out that that all BGS-computable queries are fixed by strong extension properties.
Although the BGS model is able to do arithmetic, it is unable to compute unbounded cardinalities withing a fixed number of steps. The remainder of the paper is devoted to a proof of a stronger result from Shelah [loc. cit.]: Let \(\Pi\) be a BGS program (producing a Boolean output) such that for any input, there is a polynomial bound on the number of active elements. Then there exists a class \(\mathcal C\) of signa (of asymptotic probability 1), a Boolean value \(v\) and an integer \(m\) such that for each input from \(\mathcal C\), either \(\Pi\) halts in precisely \(m\) steps and outputs \(v\) or it doesn’t halt at all. The proof relies on extensive dissection of BGS computations.
Reviewer: Gregory Loren McColm (Tampa)
MSC:
| 03D10 | Turing machines and related notions |
| 68Q19 | Descriptive complexity and finite models |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 03C13 | Model theory of finite structures |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
Keywords:
extension axioms; zero-one laws; choiceless polynomial time machine; choiceless polynomial space; constant time computable; parallel computation; random structure; random signaReferences:
| [1] | DOI: 10.1016/S0168-0072(99)00005-6 · Zbl 0936.03037 · doi:10.1016/S0168-0072(99)00005-6 |
| [2] | DOI: 10.1002/jgt.3190030305 · Zbl 0418.05050 · doi:10.1002/jgt.3190030305 |
| [3] | Bulletin of the European Association for Theoretical Computer Science 72 pp 103– (2000) |
| [4] | Computer science logic 2000 1862 pp 18– (2000) |
| [5] | Proceedings of all-union seminar on discrete mathematics and its applications (Moscow 1984) pp 56– (1986) |
| [6] | DOI: 10.1007/3-540-44622-2_6 · doi:10.1007/3-540-44622-2_6 |
| [7] | Van Nostrand (1955) |
| [8] | Proceedings of the 5th IEEE symposium on logic in computer science pp 156– (1990) |
| [9] | DOI: 10.1016/0890-5401(90)90065-P · Zbl 0708.03004 · doi:10.1016/0890-5401(90)90065-P |
| [10] | Information Processing Letters 33 pp 305– (1989) |
| [11] | Specification and validation methods pp 9– (1995) |
| [12] | Probabilities on finite models 41 pp 50– (1976) |
| [13] | Cybernetics 5 pp 142– (1969) · Zbl 0978.01027 |
| [14] | Finite model theory (1995) |
| [15] | DOI: 10.1214/aoms/1177729330 · Zbl 0048.11804 · doi:10.1214/aoms/1177729330 |
| [16] | Random graphs (1985) |
| [17] | DOI: 10.1016/S0019-9958(85)80027-9 · Zbl 0608.68077 · doi:10.1016/S0019-9958(85)80027-9 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
