Every polynomial-time 1-degree collapses if and only if P = PSPACE

Journal of Symbolic Logic 69 (3):713-741 (2004)

A set A is m-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 ∈ 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: P = PSPACE. Every two 1-equivalent sets are p-isomorphic. Every two p-invertible equivalent sets are p-isomorphic.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI http://projecteuclid.org/euclid.jsl/1096901763
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,131
Through your library

References found in this work BETA

Creative Sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.
Creative Sets.John Myhill - 1955 - Mathematical Logic Quarterly 1 (2):97-108.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Multifunction Algebras and the Provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
Polynomial-Time Abelian Groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
Relating the Bounded Arithmetic and Polynomial Time Hierarchies.Samuel R. Buss - 1995 - Annals of Pure and Applied Logic 75 (1-2):67-77.
Polynomial Games and Determinacy.Tomoyuki Yamakami - 1996 - Annals of Pure and Applied Logic 80 (1):1-16.
Feasible Graphs with Standard Universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 94 (1-3):21-35.
Rings of Monoids Elementarily Equivalent to Polynomial Rings.Gérard Leloup - 1994 - Annals of Pure and Applied Logic 68 (2):173-180.
On Polynomial-Time Relation Reducibility.Su Gao & Caleb Ziegler - 2017 - Notre Dame Journal of Formal Logic 58 (2):271-285.
Light Affine Lambda Calculus and Polynomial Time Strong Normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Characterizing PSPACE with Pointers.Isabel Oitavem - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
Characterizing PSPACE with Pointers.Isabel Oitavern - 2008 - Mathematical Logic Quarterly 54 (3):323-329.
The Analytic Polynomial-Time Hierarchy.Herbert Baier & Klaus W. Wagner - 1998 - Mathematical Logic Quarterly 44 (4):529-544.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.


Added to PP index

Total views
37 ( #212,690 of 2,237,233 )

Recent downloads (6 months)
19 ( #37,206 of 2,237,233 )

How can I increase my downloads?


My notes

Sign in to use this feature