Day 11

Finished proof of Immerman-Szelepcsényi. Links in last post.

Defined oracle Turing machines and the Baker-Gill-Solovay result that there exist oracles A and B such that

• P^A = NP^A
• P^B ≠ NP^B

Links:

Relativizations of the P =? NP Question by Baker, Gill and Solovay

You can simply take A to be any PSPACE-complete problem. For B, here is a good write-up.