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