3 ms·
Lol. The polynomial hierarchy would collapse if GI was NP-Complete, but all efforts to prove that have failed. If anything, the distance from P to NP is growing
by Ar-Curunir 11y ago
Lol. The polynomial hierarchy would collapse if GI was NP-Complete, but all efforts to prove that have failed. If anything, the distance from P to NP is growing.
- lovboat 11y agoYou can shrink an interval [a,b] by two methods [a,b'] with b'<b or [a',b] with a'> a, what you see is [a,b'] (NP-complete seem easier or lower in the difficulty scale), what I see is [a',b] that is P cover a lot more ground, I think P will cover all NP-complete problems and then the interval becomes a unique point. If [P,NP-c] = [0,1] I see GI as 1/4, if GI is proven to be in P then I should say [P,NP-c] is now [1/4,1]. In order to reduce more that interval one should find a problem that people think has a probability of 0.5 to be in P and 0.5 to be in NP, if it is proven that problem is in P then the interval get reduced a lot more. Just trying to explain my perception of the intuitive complexity of algorithms.