Could you direct me to some readable treatments of Mahaney's theorem? The best thing I've been able to find is Fortnow's lecture. I'm especially interested in discussion around the theorem and its ramifications. Thanks
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
Here's how it works:
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Kozen's Theory of Computation, Theorem 29.2 (on Google Books).
Alan Selman (editor) Complexity Theory Retrospective, Theorem 5.2.1 (on Google Books).