Journal of Symbolic Logic 68 (1):65-131 (2003)
This paper developed from Shelah's proof of a zero-one law for the complexity class "choice-less 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
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
References found in this work BETA
Choiceless Polynomial Time.Andreas Blass, Yuri Gurevich & Saharon Shelah - 1999 - Annals of Pure and Applied Logic 100 (1-3):141-187.
Citations of this work BETA
No citations found.
Similar books and articles
Identity Crises and Strong Compactness.Arthur W. Apter & James Cummings - 2000 - Journal of Symbolic Logic 65 (4):1895-1910.
Every Polynomial-Time 1-Degree Collapses If and Only If P = Pspace.Stephen A. Fenner, Stuart A. Kurtz & James S. Royer - 2004 - Journal of Symbolic Logic 69 (3):713-741.
Polynomial Time Operations in Explicit Mathematics.Thomas Strahm - 1997 - Journal of Symbolic Logic 62 (2):575-594.
Time Polynomial in Input or Output.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (3):1083-1088.
The Expressive Power of Fixed-Point Logic with Counting.Martin Otto - 1996 - Journal of Symbolic Logic 61 (1):147-176.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Proving Theorems of the Second Order Lambek Calculus in Polynomial Time.Erik Aarts - 1994 - Studia Logica 53 (3):373 - 387.
On Polynomial Time Computation Over Unordered Structures.Andreas Blass, Yuri Gurevich & Saharon Shelah - 2002 - Journal of Symbolic Logic 67 (3):1093-1125.
Added to index2009-01-28
Total downloads13 ( #350,328 of 2,158,887 )
Recent downloads (6 months)1 ( #353,783 of 2,158,887 )
How can I increase my downloads?