I was reading the Wikipedia page Random self-reducibility and it states:

If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$.

I am trying to understand that statement. It seems to say if we find a problem where a random instance is hard it would prove a bunch of complexity classes are equal. Is this correct? Which complexity classes?

  • $\begingroup$ 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 $\endgroup$ Jan 8 '18 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.