5
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\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$
    – Artur Riazanov
    Commented Jan 8, 2018 at 5:16

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Lovely answer for "what is random self reduciability?" which sadly, was not the question. $\endgroup$
    – Meir Maor
    Commented Aug 16, 2022 at 6:21
  • $\begingroup$ @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 . $\endgroup$
    – Emil Jeřábek
    Commented Aug 16, 2022 at 7:03
  • $\begingroup$ 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. $\endgroup$
    – Meir Maor
    Commented Aug 16, 2022 at 12:05
  • $\begingroup$ 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. $\endgroup$
    – user1338
    Commented Aug 16, 2022 at 13:28
-2
$\begingroup$

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}$

diagram of heirarchy

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.