4 ms·
You 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 difficult
by lovboat 11y ago
You 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.