Maybe, but that feels significantly more exotic and unlikely to me. You have to basically negate the natural cost scaling of brute force in the thousand to million n range but lose that speed benefit later.
Well, if someone found a quasipolynomial time algorithm – O(n^log(n)) – for an NP-complete problem, that would technically be compatible with P!=NP, but might have quite significant practical implications.
To have a really big impact you'd have to have that be the dominating factor at lower n and keep that "log(n)" part of the equation below 10 or so for all practical n. The latter one in particular seems unlikely to me.
[–] Dylan16807 3 days ago
[–] skissane 2 days ago
[–] Dylan16807 2 days ago