7
$\begingroup$

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 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?

Improve this question
$\endgroup$
7
  • $\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$
    – Ross Churchley
    Commented Dec 11, 2010 at 19:55
  • 1
    $\begingroup$ 'Pattern Recognition' seems too general a name for this problem. It sounds more like interpolation. $\endgroup$
    – Mitch
    Commented Dec 11, 2010 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$
    – Andreas Blass
    Commented Dec 11, 2010 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
    Commented Dec 12, 2010 at 0:22
  • 1
    $\begingroup$ But nibbles specified that $t$ is polynomial in $n$. (He gave $5n^3$ as a possible $t$.) $\endgroup$
    – David E Speyer
    Commented Dec 12, 2010 at 13:24

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .