**Collapsing Degrees**

*Guest post by Stuart Kurtz and Jim Royer.*

Bill Gasarch asked us to write an article about Collapsing Degrees, in the memory and honor of our coauthor, Steve Mahaney.

In 1986, Alan Selman and Steve Mahaney created the Structure in Complexity
Conference, now the Conference on Computational Complexity. But in 1986, it
was about *structure*, a term that Paul Young borrowed from computability
theory, and which has passed into disuse, but in those days defined us.

The word *structure* embodied optimism about a particular
approach to the P vs. NP problem—that its solution might be found
in through exploring structural properties of sets and
degrees. For example, Berman and Hartmanis had shown that if all
NP-complete sets are paddable, then all NP-complete sets were isomorphic
under polynomial time computable and invertable reductions, and hence P
≠ NP. Their result leveraged a structural property about specific
sets (paddability) to a structural result about degrees (the complete
polynomial time m-degree of NP consists of a single polynomial-time
isomorphism result), to obtain a complexity-theoretic result.

That summer, after the conference, Steve visited us in Chicago, beginning a long and productive collaboration. We beat around the isomorphism conjecture for several days, until Steve mentioned that it wasn't even know that a collapse happened at any nontrivial degree. We smelled blood.

Relativization provided some guidance. Berman had proven that the EXP-complete degree consisted of a single 1-li degree. If P = NP, then 1-li degrees collapse. Of course, if P = NP, our rationale for interest in the Isomorphism Conjecture was mooted, and what we really cared about was the “true” P ≠ NP case.

Our main result from that summer was that collapsing degrees existed, without requiring an additional complexity-theoretic hypothesis. Our proof involved a finite-injury priority argument, and seemed to require it.

It was a joy and a privilege to have had Steve Mahaney as a colleague and friend. Until we meet again, peace.

## No comments:

## Post a Comment