3 ms·
> This problem is equivalent to the P versus NP problem because if (unexpectedly) P = NP, then all of PH collapses to P (that is, P = PH). It should be noted t
by danharaj 8y ago
> This problem is equivalent to the P versus NP problem because if (unexpectedly) P = NP, then all of PH collapses to P (that is, P = PH).
It should be noted that the polynomial hierarchy could conceivably collapse at a higher level even if P!=NP. I wouldn't bet on it though.