Post #2298378
2026-03-02 20:11 UTC
@simontatham@hachyderm.io I'm quite out of my depth here but wouldn't "P=NP" entail that this exponent M in fact exists and that yes as a corollary there would be no algorithms that are polynomial and yet reqire an exponent of (M+1).
So maybe if you could show that there's no maximum M of polynomial-time algorithms you could show something about P=?NP.
Replies (1)
-
@simontatham@hachyderm.io 2026-03-03 07:35
@stylus@social.afront.org on the contrary, here's the nice simple construction I felt sure must exist: https://cs.stackexchange.com/q/86056 Essentially a time-bounded variant of the Halting Problem: does this program, given that input, halt in under (input size)^k steps? Clearly possible in O(n^k) time by just simulating it, but can't be done any faster, for the same kinds of reason as the full Halting Problem is uncomputable. Seems to me that that by itself disproves the existence of M. But it *doesn't* prove P≠NP by itself, because of that loophole about arbitrarily high-degree reductions.