most recent 30 from http://mathoverflow.net 2013-05-20T06:31:34Z http://mathoverflow.net/feeds/question/49056 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49056/is-pattern-recognition-np-complete nibbles 2010-12-11T16:45:30Z 2010-12-14T19:22:07Z

<p>Hello,</p> <p>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?</p> <p>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 <em>prove</em> 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?</p> <p>Even if you left that issue aside, I can't even think of approaches that could create such an A-B dichotomy.</p> <p>Is the problem possibly NP-intermediate?</p>

http://mathoverflow.net/questions/49056/is-pattern-recognition-np-complete/49344#49344 mhum 2010-12-14T03:05:12Z 2010-12-14T19:22:07Z

<p>The key phrase you are looking for is "<strong>resource-bounded Kolmogorov complexity</strong>". <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.9495" rel="nofollow">This paper</a> by Allender, et. al. may be a good starting point. Also, <a href="http://www.research.rutgers.edu/~troyjlee/thesis.html" rel="nofollow">this PhD thesis</a> might provide some helpful background.</p> <p><em>Edited to add</em>:</p> <p>According to the first article, <a href="http://portal.acm.org/citation.cfm?id=92591" rel="nofollow">Ko, K.-I. "On the complexity of learning minimum time-bounded Turing machines", <em>SIAM Journal on Computing</em>, 20 (1991)</a> 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.</p>