# 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