Satz von Baker, Gill und Solovay
Der Satz von Baker, Gill und Solovay besagt, dass es Orakel A und B gibt, sodass P^A=NP^A und P^B != NP^B ist. Eine wichtige Konsequenz daraus ist, dass ein Beweis für P versus NP nicht relativierbar sein kann. Das schließt gewisse elementare Beweistechniken aus, zum Beispiel Diagonalisierung.