Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,664 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesArthur 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.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
