Every polynomial-time 1-degree collapses iff P = PSPACE

Steven A. Fenner, Stuart A. Kurtz, James A. Royer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE Computer Society
Pages624-629
Number of pages6
ISBN (Print)0818619821, 9780818619823
DOIs
StatePublished - 1989
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: Oct 30 1989Nov 1 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

Other30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period10/30/8911/1/89

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Every polynomial-time 1-degree collapses iff P = PSPACE'. Together they form a unique fingerprint.

  • Cite this

    Fenner, S. A., Kurtz, S. A., & Royer, J. A. (1989). Every polynomial-time 1-degree collapses iff P = PSPACE. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 624-629). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE Computer Society. https://doi.org/10.1109/sfcs.1989.63545