(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 coc.e.?
(For more information see this
post of mine.)
If you know theorems that are less interesting because they are more interesting,
then please comment.

Posted By GASARCH to
Computational Complexity at 9/23/2010 11:00:00 AM