# Random self reducibility and NP

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?

• 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 Jan 8, 2018 at 5:16

It isn't necessarily that a random instance is hard, it's self-reducibility. The idea is that if you have, e.g., a DLP (discrete logarithm problem) instance, and you have a random function that will reduce any DLP instance to another, randomly generated one, then that is random self-reducibility. The concept might be useful if, e.g., you want to obtain "new instances" that have a known relationship to a particular hard problem you have. If you think your problem instance is hard but a random instance might be easier, you might try a random self-reduction to obtain a "gentler" instance that, while being related to your original instance in a way you may understand, is also easier for your techniques you have available to solve.

So your statement says: If every instance of an NP-complete problem can be randomly reduced to a different instance of that same problem, then the polynomial hierarchy collapses to the level you wrote down.

• Lovely answer for "what is random self reduciability?" which sadly, was not the question. Aug 16, 2022 at 6:21
• @MeirMaor The random self-reducibility is the only potentially research-level part of the question. If your question was actually intended to be “what is $\Sigma_3$”, then it is off topic, and should have been asked at cs.stackexchange.com . Aug 16, 2022 at 7:03
• The real question is what does it mean for it to collapse, and implications to assess likelihood of that, to assess viability of a a problem with hard random instances.But that was my question several years ago, now somebody else put a bounty on it and may have another focus. Aug 16, 2022 at 12:05
• I was correcting your apparently unclear understanding of random self-reducibility. I speak English quite well and answered your question in an excellent manner; if you don't feel a sense of gratitude, maybe you shouldn't try to warp reality and change what the question obviously said according to you.
– user1338
Aug 16, 2022 at 13:28

This is based on Artur Riazanov comments and the links he provided:

The Polynomial heirarchy defines a family of comlexity classes: https://en.wikipedia.org/wiki/Polynomial_hierarchy

The classes can be defined recursively by augmenting turing machines(or Non deterministic ones) with an Oracle for solving a complete problem from a lower class.

Let $$P^A$$ be the set of decision problems solvable in polynomial time by a Turing machine augmented by an oracle for some complete problem in class A. $$NP^A$$ would be the same but with a Non deterministic machine. And $$coNP^A$$ would be same with the complement.

The herirarchy then be defined to be $$\Delta^P_0 := \Sigma^P_0 := \Pi^P_0 := P$$

$$\Delta^P_{i+1} := P^{\Sigma^P_i}$$

$$\Sigma^P_{i+1} := NP^{\Sigma^P_i}$$

$$\Pi^P_{i+1} := coNP^{\Sigma^P_i}$$ When we say the polynomial heirarchy collapses it means we don't produce stronger complexity classes by going up but it stops at the 3rd level with everything being equal. $$\Pi^P_3 = \Sigma^P_3 = \Delta^P_3 = PH$$ PH being the union of all complexity classes in the heirarchy.

It has been shown that if an NP-hard random self reduciable problem exists the polynomial herirarchy collapses to the 3rd level as explained.

This can be used as an argument against the existance of such a problem.

A collapse at a lower level would be more interesting and surprising, e.g is Co-NP=NP we get a collapse at the 2nd level and PH=NP. A lower collapse still would require P=NP.