Hello,

is the problem of pattern recognition (for a given sequence of n numbers, find the shortest Turing machine with an alphabet of 42 elements that will output these n numbers in, say, 5*n^3 time) an NP-complete problem?

To me, it seems practically impossible that the problem is in P: If you had the level of understanding of algorithms required to show quickly that all algorithms smaller than this-or-that size will produce a different output or require more than 5n^3 time, what reasons could there be that prevent you from having the level of understanding required to solve the Halting problem? (in this case, actually, the problem of determining whether a program will run in less than 5n^3 steps) But I have no clue how you could possibly prove this. On the one hand, this seems to be for exactly the same reason: If you use the method "cleverly encode your SAT problem as a pattern; then prove that if the SAT instance is satisfiable, you could use a Turing machine of form A; if it is not satisfiable, you must use a longer Turing machine of form B" (or vice versa), how do you want to show that there exists no Turing machine C that is smaller than both of them? And: If you had the understanding to prove that, how could you possibly not be able to solve the Halting problem?

Even if you left that issue aside, I can't even think of approaches that could create such an A-B dichotomy.

Is the problem possibly NP-intermediate?