**THE QUESTION ASKED** >• When, in the history of mathematics, have problems "like P vs. NP" arisen and then been solved?<br> > • 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](http://mathoverflow.net/questions/160265/analogues-of-p-vs-np-in-the-history-of-mathematics/160349#comment409901_160349)) 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](http://en.wikipedia.org/wiki/Mark_I_Fire_Control_Computer), and was fictionally addressed in charming stories such as E. E. "Doc" Smith's [*The Vortex Blaster*](http://en.wikipedia.org/wiki/The_Vortex_Blaster#Plot_synopsis). This same provenance is naturally framed in the terms of the question-asked as "<strike> Mathematicians </strike> *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](http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no). 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](http://en.wikipedia.org/wiki/Low-density_parity-check_code#Decoding), 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?](http://cstheory.stackexchange.com/questions/11691/does-p-contain-languages-whose-existence-is-independent-of-pa-or-zfc-tcs-commu)."