Monday, September 18, 2017

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
  • PA = NPA
  • PB ≠ NPB
  • 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