<p>This is based on Artur Riazanov comments and the links he provided:</p>
<p>The Polynomial heirarchy defines a family of comlexity classes:
<a href="https://en.wikipedia.org/wiki/Polynomial_hierarchy" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Polynomial_hierarchy</a></p>
<p>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.</p>
<p>Let <span class="math-container">$P^A$</span> 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.
<span class="math-container">$NP^A$</span> would be the same but with a Non deterministic machine.
And <span class="math-container">$coNP^A$</span> would be same with the complement.</p>
<p>The herirarchy then be defined to be
<span class="math-container">$\Delta^P_0 := \Sigma^P_0 := \Pi^P_0 := P$</span></p>
<p><span class="math-container">$\Delta^P_{i+1} := P^{\Sigma^P_i}$</span></p>
<p><span class="math-container">$\Sigma^P_{i+1} := NP^{\Sigma^P_i}$</span></p>
<p><span class="math-container">$\Pi^P_{i+1} := coNP^{\Sigma^P_i}$</span></p>
<p><a href="https://i.sstatic.net/AD5IS.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/AD5IS.png" alt="diagram of heirarchy" /></a></p>
<p>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. <span class="math-container">$\Pi^P_3 = \Sigma^P_3 = \Delta^P_3 = PH$</span>
PH being the union of all complexity classes in the heirarchy.</p>
<p>It has been shown that if an NP-hard random self reduciable problem exists the polynomial herirarchy collapses to the 3rd level as explained.</p>
<p>This can be used as an argument against the existance of such a problem.</p>
<p>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.</p>

CC BY-SA 4.0
2022-08-16T06:54:58.487Z
2022-08-16T06:54:58.487Z
Meir Maor
<p>I was reading the Wikipedia page <a href="https://en.wikipedia.org/wiki/Random_self-reducibility" rel="nofollow noreferrer">Random self-reducibility</a> and it states: </p>

<blockquote>
  <p>If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to <span class="math-container">$\Sigma_3$</span>.</p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2018-01-08T05:16:28.933Z
The wikipedia article seems to be based on the paper http://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 https://en.wikipedia.org/wiki/Polynomial_hierarchy
Artur Riazanov
<np-hardness><complexity-classes><reductions>
Random self reducibility and NP
Meir Maor
# Random self reducibility and NP

(Asked by: username_0 on 2018-01-01)

I was reading the Wikipedia page [Random self-reducibility](https://en.wikipedia.org/wiki/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?

**Tags:** np-hardness, complexity-classes, reductions

> **Comments:**
> **username_1**: The wikipedia article seems to be based on the paper http://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 https://en.wikipedia.org/wiki/Polynomial_hierarchy  

---

## 1 answers

### Answer by username_0 on 2022-08-16. Score: -2

This is based on username_1 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](https://i.sstatic.net/AD5IS.png)](https://i.sstatic.net/AD5IS.png)

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.


---

