The Polynomial Hierarchy, what is it?

Here we introduce the notion of "polynomial hierarchy" as a technique to try to separate P and NP. If P = NP, what else is in it? - the polynomial hierarchy! This is also a technique to try to separate P/NP and PSPACE.

Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Timmy Gy, Josh Hibschman, Patrik Keinonen, Travis Schnider, and Tao Su

Merch:

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

[EasyTheory]

Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are in the video description. Names are listed in alphabetical order by surname.
Platinum: Micah Wood
Silver: Simone Glinz, Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su


Addendum: forgot to explain the arrows! If an arrow is x -> y, then x is a subset of y. For example, P subset NP, NP subset NP^NP, etc. However, it's not totally obvious that coNP is a subset of NP^NP, because we don't know the relation between NP and coNP. The trick is to phrase these collections of languages in a different way, in that the "ith layer" on the "NP side" corresponds to Exists x1 Forall x2 ... Qi xi [formula], and the "coNP" side is the same but starts with Forall instead of Exists. Then it's easy to show that coNP is a subset of NP^NP. (Now one needs to show that these two definitions--the one in the video, and this one--are equivalent first.)