### 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 language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | IEEE Computer Society |

Pages | 624-629 |

Number of pages | 6 |

ISBN (Print) | 0818619821, 9780818619823 |

DOIs | |

State | Published - 1989 |

Event | 30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA Duration: Oct 30 1989 → Nov 1 1989 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | 30th Annual Symposium on Foundations of Computer Science |
---|---|

City | Research Triangle Park, NC, USA |

Period | 10/30/89 → 11/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

*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