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 5*n^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 5*n^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?

  • $\begingroup$ In order for a problem to be NP-complete or NP-intermediate, it has to itself be in NP. Do you have reason to believe this problem is in NP? I'm not entirely convinced that it's even computable... $\endgroup$ Dec 11 '10 at 19:55
  • 1
    $\begingroup$ 'Pattern Recognition' seems too general a name for this problem. It sounds more like interpolation. $\endgroup$
    – Mitch
    Dec 11 '10 at 20:06
  • $\begingroup$ Perhaps the time bound (like 5*n^3) should be in terms of the total length (in digits) of the desired output rather than in terms of n. That way, with a reasonable bound, there will be some program producing the right output (e.g., just a print command) and the problem is just to find the shortest one, as opposed to having to worry about whether such a program exists at all. $\endgroup$ Dec 11 '10 at 20:13
  • 5
    $\begingroup$ If you formulate the problem as "Given a list of n numbers and bounds k and t, does there exist a Turing machine of size at most k which outputs these numbers in time at most t?" then the problem will be in NP: the proof certificate is just the Turing machine, which we simulate for time t to check that it outputs the desired numbers. $\endgroup$
    – Tom Church
    Dec 12 '10 at 0:22
  • 1
    $\begingroup$ But nibbles specified that $t$ is polynomial in $n$. (He gave $5n^3$ as a possible $t$.) $\endgroup$ Dec 12 '10 at 13:24

The key phrase you are looking for is "resource-bounded Kolmogorov complexity". This paper by Allender, et. al. may be a good starting point. Also, this PhD thesis might provide some helpful background.

Edited to add:

According to the first article, Ko, K.-I. "On the complexity of learning minimum time-bounded Turing machines", SIAM Journal on Computing, 20 (1991) may be even more relevant. In that paper, Ko demonstrates that determining whether or not computing time-bounded Kolmogorov complexity is NP-hard requires non-relativizing techniques.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.