Arrow Research search

Author name cluster

James S. Royer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
2 author rows

Possible papers

5

FOCS Conference 1989 Conference Paper

Every Polynomial-Time 1-Degree Collapses iff P=PSPACE

  • Stephen A. Fenner
  • Stuart A. Kurtz
  • James S. Royer

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 in A if and only if f(x) in B. Two sets are 1-equivalent if 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. >

Details

FOCS Conference 1986 Conference Paper

Collapsing Degrees (Extended Abstract)

  • Stuart A. Kurtz
  • Stephen R. Mahaney
  • James S. Royer

An m-degree is a collection of sets equivalent under polynomial-time many-one (Karp) reductions; for example, the complete sets for NP or PSPACE are m-degrees. An m-degree is collapsing iff its members are p-isomorphic, i. e. , equivalent under polynomial time, 1-1, onto, polynomial time invertible reductions. L. Berman and J. Hartmanis showed that all the then known natural NP-complete sets are isomorphic, and conjectured that the m-degree of the NP-complete sets collapses, in essence claiming that there is only one NP-complete set. However, until now no nontrivial collapsing m-degree was known to exist. In this paper we provide the first examples of such degrees, In particular, we show that there is a collapsing degree which is btt-complete for EXP (the exponential time decidable sets) and that, for every set A, there is a collapsing degree which is hard for A. We also obtain analogous results for noncollapsing degrees.

Details