0

Assume that P1, P2,..., Pn are NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be reduced to PP1 in polynomial time, then PP1 can be reduced to PP2, and PP2 can be reduced to another NP problem in polynomial time.

What will be the classes of PP1 and PP2 ? In my opinion both PP1 and PP2 should be NP complete. As PP1 is reduced to NP problem and it can be as hard as Np so it should be NP Complete. PP2 is reduced from PP1 that means it can be as hard as PP1 so it will be NP Hard but now PP2 is also reduced to NP Problem. So it should as hard as NP so it should be NP complete. Tell Me if I am wrong.

Bernard
  • 175,478
Nishita Patnaik
  • 3

1 Answers1

1

Since $P_1, P_2, ..., P_n$ can be reduced to $PP_1$, then they are included in $PP_1$'s class.

Since $PP_1$ reduces to $PP_2$, then $PP_1$ is in $PP_2$'s complexity class.

Since $PP_2$ can be reduced to an $NP$ problem, then $PP_2$ is in $NP$.

Therefore, $PP_1$ is also in $NP$ by transitivity.

There is no information to conclude that some of these problems are $NP$-complete, for proving that some problem $PP$ is $NP$-complete you need to show that a reduction from any problem in $NP$ to $PP$ exists.

If, for example, some problem among $P_1, P_2, ..., P_n$ was $NP$-complete, then you would be right, since it reduces to $PP_1$ (and $PP_2$ by transitivity) which along with $PP_1$ and $PP_2$ being in $NP$ as shown before, gives the definition of $NP$-completeness.

ObliviousCapybara
  • 487