1659[Computational Complexity] Theorems that are less interesting because they ar...
- Sep 23, 2010(This post was inspired by Joe Kruskal's passing. Kruskal's tree theorem, trees under minor are a well quasi order, relates to example 2 below.)
There are some theorems that seem less interesting once you generalize them. I am not sure they are less interesting, but they seem that way. Here are some.
- In 1978 I told my number theory professor that there is a polynomial in many variables with integer coefficients such that the positive numbers in the image are exactly the primes. He thought that was interesting! Maybe it uses algebraic number theory! or cyclotomic fields! or some deep number theory! I then told him that for any r.e. set A there is a polynomial in many variables with integer coefficients such that the positive numbers in that set is exactly A. You prove this by coding Turing Machines into polynomials. No hard number theory needed. It uses some easy number theory and many tricks. He was much less interested. (The result comes from the machinery used to prove Hilbert's Tenth Problem.) Jones came up with the actual polynomial. See here.)
- It easy to show that if L is regular (CFL, c.e.) then SUBSEQ(L) is regular (CFL, c.e.). What about if L is decidable? The good news: if L is decidable then SUBSEQ(L) is decidable. That sounds surprising and interesting. It is not. Actually if L is any language whatsoever then SUBSEQ(L) is regular. (High Level Proof: subsequence is a well quasi ordering, hence any downwardly closed subset of Σ*, such as SUBSEQ(L), has a finite obstruction set. This finite obstruction set can be used to give a DFA for SUBSEQ(L).) What I really want to see is a proof of L decidable implies SUBSEQ(L) is decidable that comes from recursion theory. I don't have one. I'm not even sure what that would mean. Show that SUBSEQ(L) is both c.e. and co-c.e.? (For more information see this post of mine.)
Posted By GASARCH to Computational Complexity at 9/23/2010 11:00:00 AM