# Random self reducibility and NP

If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $$\Sigma_3$$.
• The wikipedia article seems to be based on the paper people.cs.uchicago.edu/~fortnow/papers/rsr.pdf It has formal definitions for all the objects involved. The result about polynomial hierarchy is Theorem 3.1 (and Corollary 3.3). The statement "polynomial hierarchy collapses to $\Sigma_3^P$ is equivalent to $\Sigma_3^P = \Pi_3^P$ or $\Sigma_3^P = \mathbf{PH}$. Definitions of these classes could be found at en.wikipedia.org/wiki/Polynomial_hierarchy – Artur Riazanov Jan 8 '18 at 5:16