Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-01-10T21:37:33.296Z Has data issue: false hasContentIssue false
  • English
  • Français

Strong extension axioms and Shelah's zero-one law for choiceless polynomial time

Published online by Cambridge University Press:  12 March 2014

Andreas Blass  and
Yuri Gurevich
Andreas Blass
Affiliation:
Mathematics Department, University of Michigan, Ann Arbor, MI 48109-1109, USA, E-mail: [email protected]
Yuri Gurevich
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper developed from Shelah's proof of a zero-one law for the complexity class “choiceless polynomial time,” defined by Shelah and the authors. We present a detailed proof of Shelah's result for graphs, and describe the extent of its generalizability to other sorts of structures. The extension axioms, which form the basis for earlier zero-one laws (for first-order logic, fixed-point logic, and finite-variable infinitary logic) are inadequate in the case of choiceless polynomial time; they must be replaced by what we call the strong extension axioms. We present an extensive discussion of these axioms and their role both in the zero-one law and in general.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 68 , Issue 1 , March 2003 , pp. 65 - 131
Copyright
Copyright © Association for Symbolic Logic 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Blass, Andreas and Gurevich, Yuri, Choiceless polynomial time computation and the zero-one law, Computer science logic 2000 (Clote, Peter and Schwichtenberg, Helmut, editors), Lecture Notes in Computer Science, vol. 1862, Springer, 2000, pp. 18–40.Google Scholar
[2]Blass, Andreas, A new zero-one law and strong extension axioms, Bulletin of the European Association for Theoretical Computer Science, vol. 72 (2000), pp. 103–122.Google Scholar
[3]Blass, Andreas, Gurevich, Yuri, and Kozen, Dexter, A zero-one law for logic with a fixed-point operator, Information and Control, vol. 67 (1985), pp. 70–90.CrossRefGoogle Scholar
[4]Blass, Andreas, Gurevich, Yuri, and Shelah, Saharon, Choiceless polynomial time, Annals of Pure and Applied Logic, vol. 100 (1999), pp. 141–187.CrossRefGoogle Scholar
[5]Blass, Andreas and Harary, Frank, Properties of almost all graphs and complexes, Journal of Graph Theory, vol. 3 (1979), pp. 225–240.CrossRefGoogle Scholar
[6]Bollobás, Béla, Random graphs, Academic Press, 1985.Google Scholar
[7]Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Annals of Mathematical Statistics, vol. 23 (1952), pp. 493–507.CrossRefGoogle Scholar
[8]Ebbinghaus, Heinz-Dieter and Flum, Jörg, Finite model theory, Springer-Verlag, 1995.Google Scholar
[9]Fagin, Ron, Probabilities on finite models, this Journal, vol. 41 (1976), pp. 50–58.Google Scholar
[10]Glebskii, Y. V., Kogan, D. I., Liogonkii, M. I., and Taianov, V. A., Range and degree of realizability of formulas in the restricted predicate calculus, Cybernetics, vol. 5 (1969), pp. 142–154.CrossRefGoogle Scholar
[11]Gurevich, Yuri, Evolving algebras 1993: Lipari guide, Specification and validation methods (Börger, E., editor), Oxford University Press, 1995, pp. 9–36. See also the May 1997 draft of the ASM guide, Tech Report CSE-TR-336-97, EECS Dept., Univ. of Michigan, 1997. Found at: http://www.eecs.umich.edu/gasm/.Google Scholar
[12]Hagerup, Torben and Rüb, Christine, A guided tour of Chernoff bounds, Information Processing Letters, vol. 33 (1989/1990), pp. 305–308.CrossRefGoogle Scholar
[13]Kolaitis, Phokion and Vardi, Moshe, 0-1 laws and decision problems for fragments of secondorder logic, Information and Computation, vol. 87 (1990), pp. 302-339, (special issue for the 3rd IEEE Symposium on Logic in Computer Science, 1988).CrossRefGoogle Scholar
[14]Kolaitis, Phokion and Vardi, Moshe, 0-1 laws for infinitary logics, Proceedings of the 5th IEEE symposium on logic in computer science, 1990, pp. 156-167.Google Scholar
[15]Loeve, M., Probability theory, Van Nostrand, 1955.Google Scholar
[16]Shelah, Saharon, Choiceless polynomial time logic: inability to express [paper number 634], Computer science logic 2000 (Peter Clote and Helmut Schwichtenberg, editors), Lecture Notes in Computer Science, vol. 1862, Springer, 2000, pp. 72-125.CrossRefGoogle Scholar
[17]Talanov, V. A. and Knyazev, V. V., The asymptotic truth of infinite formulas, Proceedings of all-union seminar on discrete mathematics and its applications (Moscow 1984), 1986, pp. 56-61.Google Scholar