Math Table/Open Neighborhood Seminar: Superpowers and relativization in the theory of computational complexity

MATH TABLE

Speaker:

Noah Singer - Harvard Undergraduate

Proving a result that’s more general than intended can often be a cause to celebrate! But it can also be a red flag, indicating that a particular technique is not incisive enough to tackle more advanced problems. In this talk, we’ll see one such situation, the notion of relativization in the theory of computational complexity. We’ll define what it means for a theorem to relativize — hold true even if computers are given superpowers — and describe the famous P vs. NP problem and why it cannot be resolved by relativizing techniques. If we have time, we’ll sketch a proof of the time hierarchy theorem, a nice example of a relativizing theorem.

Zoom: https://harvard.zoom.us/j/96759150216?pwd=Tk1kZlZ3ZGJOVWdTU3JjN2g4MjdrZz09