Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-07T20:08:24.344Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  12 March 2014

Stephen A. Fenner ,
Stuart A. Kurtz  and
James S. Royer
Stephen A. Fenner
Affiliation:
Dept. of Computer Science, University of South Carolina, Columbia, SC 29208, USA, E-mail: [email protected]
Stuart A. Kurtz
Affiliation:
Dept. of Computer Science, University of Chicago, 1100 E. 58TH ST., Chicago, IL 60637-1581, USA, E-mail: [email protected]
James S. Royer
Affiliation:
Dept. of Elec. Eng. and Computer Science, Syracuse University, Syracuse, NY 13244, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 69 , Issue 3 , September 2004 , pp. 713 - 741
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.)

References

REFERENCES

[Ben89]Bennett, C., Time/space trade-offs for reversible computation, SIAM Journal on Computing, vol. 18 (1989), pp. 766–776.CrossRefGoogle Scholar
[Ber77]Berman, L., Polynomial reducibilities and complete sets, Ph.D. thesis, Cornell University, 1977.Google Scholar
[BH77]Berman, L. and Hartmanis, J., On isomorphism and density of NP and other complete sets, SIAM Journal on Computing, vol. 1 (1977), pp. 305–322.CrossRefGoogle Scholar
[Ded88]Dedekind, R., Was sind und was sollen die Zahlen?, Vieweg, 1888, English translation in [Ewa96], Vol. 2.Google Scholar
[Dow82]Dowd, M., Isomorphism of complete sets, Technical Report LCSR-TR-34, Laboratory for Computer Science Research, Rutgers University, Busch Campus, 1982.Google Scholar
[Ewa96]Ewald, W. (editor), From Kant to Hilbert: A sourcebook in the foundations of mathematics, Oxford University Press, 1996, in two volumes.Google Scholar
[Fer99]Ferreirós, J., Labyrinth of thought: A history of set theory and its role in modern mathematics, Birkhäuser, 1999.CrossRefGoogle Scholar
[GH89]Ganesan, K. and Homer, S., Complete problems and strong polynomial reducibilities, Proceedings of the symposium on theoretical aspects of computer science, Springer-Verlag, 1989, pp. 240–250.Google Scholar
[GJ79]Garey, M. and Johnson, D., Computers and intractability, W. H. Freeman and Company, 1979.Google Scholar
[GS84]Grollmann, J. and Selman, A., Complexity measures for public-key cryptosystems, Proceedings of the 25th annual ieee symposium on foundations of computer science, IEEE Computer Society, 1984, pp. 495–503.Google Scholar
[GS88]Grollmann, J. and Selman, A., Complexity measures for public-key cryptosystems, SIAM Journal on Computing, vol. 17 (1988), pp. 309–335.CrossRefGoogle Scholar
[HKR93]Homer, S., Kurtz, S., and Royer, J., On many-one and 1-truth-table complete sets, Theoretical Computer Science, vol. 115 (1993), pp. 383–389.CrossRefGoogle Scholar
[Ko85]Ko, K., On some natural complete operators, Theoretical Computer Science, vol. 37 (1985), pp. 1–30.CrossRefGoogle Scholar
[KLD87]Ko, K., Long, T., and Du, D., A note on one-way functions and polynomial-time isomorphisms, Theoretical Computer Science, vol. 47 (1987), pp. 263–276.CrossRefGoogle Scholar
[KMR90]Kurtz, S., Mahaney, S., and Royer, J., The structure of complete degrees, Complexity theory retrospective (Selman, A., editor), Springer-Verlag, 1990, pp. 108–146.CrossRefGoogle Scholar
[Moo82]Moore, G., Zermelo's axiom of choice: Its origins, development, and influence, Springer-Verlag, 1982.CrossRefGoogle Scholar
[Myh55]Myhill, J., Creative sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 1 (1955), pp. 97–108.CrossRefGoogle Scholar
[Rog67]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, 1967, Reprinted, MIT Press, 1987.Google Scholar