Login
You're viewing the mastodonapp.uk public feed.
  • Oct 29, 2026, 1:10 AM

    @sophieschmieg i kinda wish the P=NP problem gets solved in a similar way (ideally not by “AI”): either someone finds an algorithm running in O(n^{a lot}) with a prohibitive additive constant for solving NP problems (officially fast, realistically slow), or conversely someone manages to solve NP problems in time O((1 + {something small})^n) (realistically fast, officially slow). both would render the question somewhat moot 🙃

    💬 1🔄 0⭐ 0

Replies

  • Oct 29, 2026, 1:13 AM

    @sophieschmieg i mean, SAT/ILP solvers already do some nontrivial magic around that, so really in some applications the question is already irrelevant i think…

    💬 0🔄 0⭐ 0