LESSONS FROM RUNTIME CLASSIFICATION PROBLEMS
• When, in the history of mathematics, have problems "like P vs. NP" arisen and then been solved?
• In those cases, what were the resolutions?
The Runtime Fence Problem for TMs Given a Turing Machine (TM) promised to be in P, and a non-negative real runtime exponent $k$, a commonplace and eminently practical math-and-engineering question is this: "Is the TM's runtime $O(n^k)$ with respect to input length $n$?"
We call this is the Runtime Fence Problem for TMs.
The Relevance to the Question Asked We imagine that "an invisible fence" separates TMs whose runtimes are slower-than-$n^k$ from TMs whose runtimes are $n^k$-or-faster, and we are asked to decide whether a given TM resides on one side or the other.
Historical Provenance (per Henry Cohn's comment) In the decades prior to WWII, the engineering question "What maximal accuracy is compatible with real-time computation of firing solutions?" was pragmatically answered by computational devices such as the (then-secret) Mark 1 Fire Control Computer, and was fictionally addressed in charming stories such as E. E. "Doc" Smith's The Vortex Blaster.
This same provenance is naturally framed in the terms of the question-asked as " Mathematicians engineers conjectured that the two classes [of real-time versus too-slow computation processes] were unequal, but were unable to prove or disprove that for a long time."
The Resolution Emanuele Viola has proved that the Runtime Fence Problem for TMs is undecidable.
So in regard to runtime exponents, the "invisible fence" turns out to be formally invisible.
Present Practice The formal invisibility of the Runtime Fence provides scant grounds to expect that efficient, reliable, real-time computation processes---error-correction by solving NP-complete belief-propagation problems, for example---can be designed at all. And yet for reasons that remain poorly understood by engineers and mathematicians, real-time processes that solve NP-complete problems commonly are designed rationally and perform near-optimally.
NATURAL EXTENSIONS
The Runtime Fence Problem for Languages Given a language L, the Runtime Fence Problem can be posed for the most efficient TM that recognizes that language. We call this The Runtime Fence Problem for Languages.
The Resolution The Runtime Fence Problem for Languages is natural, open, apparently difficult, and conjecturally undecidable.
For definitional details, comments, and mathematical history, see the TCS StackExchange community wiki "Does P contain languages whose existence is independent of PA or ZFC?."