Every polynomial-time 1-degree collapses if and only if P = pspace
Journal of Symbolic Logic 69 (3):713-741 (2004)
| Abstract | A set A is m-reducible (or Karp-reducible) to B if and only if there is a polynomial-time computable function f such that, for all x, x ∊ A if and only if f(x) ∊ B. Two sets are: • 1-equivalent if and only if each is m-reducible to the other by one-one reductions; • p-invertible equivalent if and only if each is m-reducible to the other by one-one, polynomial-time invertible reductions; and • p-isomorphic if and only if there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. In this paper we show the following characterization. THEOREM. The following are equivalent: (a) P = PSPACE. (b) Every two 1-equivalent sets are p-isomorphic. (c) Every two p-invertible equivalent sets are p-isomorphic | |||||||||
| 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,705 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesAndreas Blass & Yuri Gurevich (2003). Strong Extension Axioms and Shelah's Zero-One Law for Choiceless Polynomial Time. Journal of Symbolic Logic 68 (1):65-131.
Erik Aarts (1994). Proving Theorems of the Second Order Lambek Calculus in Polynomial Time. Studia Logica 53 (3):373 - 387.
Kazushige Terui (2004). Light Affine Set Theory: A Naive Set Theory of Polynomial Time. Studia Logica 77 (1):9 - 40.
Maria Bulińska (2009). On the Complexity of Nonassociative Lambek Calculus with Unit. Studia Logica 93 (1).
Natacha Portier (2000). Le Problème Des granDes Puissances Et Celui Des granDes Racines. Journal of Symbolic Logic 65 (4):1675-1685.
Thomas Strahm (1997). Polynomial Time Operations in Explicit Mathematics. Journal of Symbolic Logic 62 (2):575-594.
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet (2006). Enumerations of the Kolmogorov Function. Journal of Symbolic Logic 71 (2):501 - 528.
Andreas Blass, Yuri Gurevich & Saharon Shelah (2002). On Polynomial Time Computation Over Unordered Structures. Journal of Symbolic Logic 67 (3):1093-1125.
Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. Journal of Symbolic Logic 71 (2):399 - 424.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-02-05Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
