Hacker News

points by Dylan16807 3 days ago | 0 comments

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.

[–] skissane 2 days ago

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.

[–] Dylan16807 2 days ago

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.