@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.}",
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",
note = "30th Annual Symposium on Foundations of Computer Science ; Conference date: 30-10-1989 Through 01-11-1989",
}