3 ms·
That's what's called a "non-constructive" proof in some circles. It /doesn't/ have a useful path forward, which makes it frustrating. There are some weird sandw
by tetha 3y ago
That's what's called a "non-constructive" proof in some circles. It /doesn't/ have a useful path forward, which makes it frustrating. There are some weird sandwiches of complexity classes - like, iirc, P-SPACE, EXP, NP-SPACE - which we know to have exactly 2 subsets plus the total subset, but which constellations? Dunno.
This is different from a constructive proof. "Here we have a problem, and all algorithms so far are in O(n^3). We can demonstrate the existence of a substructure in all instances of this problem which lowers the complexity to O(n^2.978)" would be a huge constructive proof in some fields. Such a breakthrough could lead to a large number of follow-up improvements.
A non-constructive breakthrough is like "Yup, this is a barrier. No clue why though, but it's hard."