Post #2298379

@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.