@inproceedings{0c22e7e230c64677abdb9f99840dfcac,

title = "Every polynomial-time 1-degree collapses iff P = PSPACE",

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 iff each is m-reducible to the other by one-one reductions; p-invertible equivalent iff each is m-reducible to the other by one-one, polynomial-time invertible reductions; and p-isomorphic iff there is an m-reduction from one set to the other that is one-one, onto, and polynomial-time invertible. It is proved that the following statements are equivalent: (1) P = PSPACE. (2) Every two 1-equivalent sets are p-isomorphic. (3) Every two p-invertible equivalent sets are p-isomorphic.",

author = "Fenner, {Steven A.} and Kurtz, {Stuart A.} and Royer, {James A.}",

note = "Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 30th Annual Symposium on Foundations of Computer Science ; Conference date: 30-10-1989 Through 01-11-1989",

year = "1989",

doi = "10.1109/sfcs.1989.63545",

language = "English (US)",

isbn = "0818619821",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "IEEE Computer Society",

pages = "624--629",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

address = "United States",

}