Graduate studies at Western
Journal of Symbolic Logic 68 (1):65-131 (2003)
|Abstract||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)|
|Through your library||Configure|
Similar books and articles
Arthur W. Apter & James Cummings (2000). Identity Crises and Strong Compactness. Journal of Symbolic Logic 65 (4):1895-1910.
Stephen A. Fenner, Stuart A. Kurtz & James S. Royer (2004). Every Polynomial-Time 1-Degree Collapses If and Only If P = Pspace. Journal of Symbolic Logic 69 (3):713-741.
Thomas Strahm (1997). Polynomial Time Operations in Explicit Mathematics. Journal of Symbolic Logic 62 (2):575-594.
Lauri Hella (1996). Logical Hierarchies in PTIME. Information and Computation 129 (1):1--19.
Yuri Gurevich & Saharon Shelah (1989). Time Polynomial in Input or Output. Journal of Symbolic Logic 54 (3):1083-1088.
Martin Otto (1996). The Expressive Power of Fixed-Point Logic with Counting. Journal of Symbolic Logic 61 (1):147-176.
Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. Journal of Symbolic Logic 71 (2):399 - 424.
Erik Aarts (1994). Proving Theorems of the Second Order Lambek Calculus in Polynomial Time. Studia Logica 53 (3):373 - 387.
Andreas Blass, Yuri Gurevich & Saharon Shelah (2002). On Polynomial Time Computation Over Unordered Structures. Journal of Symbolic Logic 67 (3):1093-1125.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Recent downloads (6 months)0
How can I increase my downloads?