The relative complexity of NP search problems.

Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi

Browse the full STOC paper archive.