Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T23:22:31.156Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  12 March 2014

Stephen A. Fenner
Affiliation:
Dept. of Computer Science, University of South Carolina, Columbia, SC 29208, USA, E-mail: fenner@cs.sc.edu
Stuart A. Kurtz
Affiliation:
Dept. of Computer Science, University of Chicago, 1100 E. 58TH ST., Chicago, IL 60637-1581, USA, E-mail: stuart@cs.uchicago.edu
James S. Royer
Affiliation:
Dept. of Elec. Eng. and Computer Science, Syracuse University, Syracuse, NY 13244, USA, E-mail: royer@ecs.syr.edu

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 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-isumorphic 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:

(a) P = PSPACE.

(b) Every two 1-equivalent sets are p-isomorphic.

(c) Every two p-invertible equivalent sets are p-isomorphic.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable