A degree is a collection of languages that can be reduced to each other using
polynomial-time computable functions. There are different sorts of degrees
corresponding to different sorts of reductions. For example, a Turing degree is
one where, for every pair of languages A and B in the degree, A can be decided
by a poly-time function that makes oracle queries to B. A many-one degree is one
where the reduction function maps strings in A to strings in B and strings
outside of A to strings outside of B without making any queries. It's easy to
see that every many-one degree is contained in a
Turing degree. A significant open question is whether there is a Turing degree
where every pair of languages is equivalent with many-one reductions? If this is
so we say that the Turing degree collapses to the many-one degree.
This talk will survey results by Ambos-Spies, et al, Beigel and Fortnow, and
Selman that limit the complexity of a language when its Turing degree collapses
to a many-one degree.