Return to Answer

Edits  The nomenclature of the original answer have been amended to parallel the (higher-rated) "Lessons from crystallographic classification;" on the grounds that both classification problems---crystallographic and runtime---are eminently practical, such that both problems were studied by engineers and scientists long before mathematicians.

These two problems are similar too in their various overlaps and natural affinities with respect to PvsNP (as the answers summarize). Henry Cohn's thoughtful remarks helped me to appreciate these parallels.

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.

Edits  The nomenclature of the original answer have been amended to parallel the (higher-rated) "Lessons from crystallographic classification;" on the grounds that both classification problems---crystallographic and runtime---are eminently practical, such that both problems were studied by engineers and scientists long before mathematicians.

These two problems are similar too in their various overlaps and natural affinities with respect to PvsNP (as the answers summarize). Henry Cohn's thoughtful remarks helped me to appreciate these parallels.

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.

The Resolution  Emanuele Viola has proved that the Runtime Classification Problem for TMs is 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?."

The Resolution  Emanuele Viola has proved that the Runtime Classification Problem for TMs is 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?."

LESSONS FROM RUNTIME CLASSIFICATION PROBLEMS

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 Resolution  Emanuele Viola has proved that the Runtime Fence Problem for TMs is undecidable.

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.

LESSONS FROM RUNTIME CLASSIFICATION

Edits  The nomenclature of the original answer have been amended to parallel the (higher-rated) "Lessons from crystallographic classification;" on the grounds that both classification problems---crystallographic and runtime---are eminently practical, such that both problems were studied by engineers and scientists long before mathematicians.

These two problems are similar too in their various overlaps and natural affinities with respect to PvsNP (as the answers summarize). Henry Cohn's thoughtful remarks helped me to appreciate these parallels.

It is plausible that the (seemingly complete) present-day resolution of the crystallographic classification problem, and the present-day partial resolution of the runtime classification problem, both may foreshadow elements of an eventual resolution of the PvsNP problem. Needless to say, it is neither necessary, nor feasible, nor even desirable, that everyone think alike in this regard.

The Question Asked

The Runtime Classification 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 Classification Problem for TMs.

The Resolution  Emanuele Viola has proved that the Runtime Classification Problem for TMs is undecidable.

The Runtime Classification Problem for Languages    Given a language L, the Runtime Classification Problem can be posed for the most efficient TM that recognizes that language. We call this The Runtime Classification Problem for Languages.

The Resolution  The Runtime Classification Problem for Languages is natural, open, apparently difficult, and conjecturally undecidable.