FOM: Why is everything linearly ordered? With a digression on "computability theory"

[JoeShipman@aol.com]

V. Shavrukov to Harvey via FOM:

" I would greatly appreciate it if you could comment on the following
 proposition:
 
 Questions like
 >1. Are PA[pi-0-n] and PA[pi-0-m] isomorphic?
 >2. Is there a nontrivial automorphism of PA[pi-0-n]?
 >3. Is the first order theory of PA[pi-0-n] decidable?
 >4. Is PA[pi-0-n] isomorphic to some {x: x >= y}?
 only have any intellectual signficance in as much as they provide
 background to the problem
 'Why is everything important linearly ordered?' "

Since this was posted on FOM I will beat Harvey to the punch: "Why is
everything important linearly ordered?" is a question of the most extreme
significance and it seems likely that the answers to Harvey's 4 questions will
be significant only if they shed light on this grand meta-question, though I
wouldn't rule out the possibility of some other intellectually significant
consequence.

It is a great mystery why all natural logical systems appear to be linearly
ordered in consistency strength.  A related mystery is why there do not appear
to be "natural" r.e. degrees of unsolvability (i.e. degrees of sets arising in
mathematics other than recursion theory) other than 0 and 0'.  This is not
quite the same mystery because even if natural degrees between 0 and 0' are
found they may still be linearly ordered.  I believe that the situation is the
same for higher degrees: that is, that no natural example is known of a set
whose degree of unsolvability is not in {0, 0', 0'', ....} [where the ....'s
run through recursive ordinals], except for sets whose degree is obviously
greater than all of these.

In the related field of computational complexity 
DIGRESSION
(which is a separate subject from recursion theory, characterized by the
notion of resource-limited computation; it used to be a sub-subject of
recursion theory but grew so explosively as to outstrip its parent and declare
independence, just as complex analysis stopped being regarded as real analysis
specialized to cases where the Cauchy-Riemann partial differential equations
were satisfied and became a subject in its own right--to legitimately classify
both computational complexity theory and recursion theory under the name
"computability theory" without offending anyone one had better be a respected
researcher in BOTH areas; such researchers exist and their conclusive opinion
on this terminological controversy is awaited)
END DIGRESSION
, there is an even more interesting mystery--because there ARE natural classes
of sets of integers which are believed to be incomparable, but nobody can
prove it!  As I may have mentioned here a few months ago, when I queried Steve
Cook about this he suggested DSPACE(log(n)^2) and PTIME as examples; if these
ARE comparable then either the satisfiability problem is solvable in log-
squared space or the group isomorphism problem (with the groups presented by
their multiplication tables) is solvable in polynomial time, and he felt both
of these were highly unlikely.  (In my opinion the latter possibility is much
more likely than the former.)

Of course we can't even prove PTIME is different from  PSPACE or LOGSPACE
though one of these must be true.  This is a terrible impasse, but is it maybe
possible that the consensus that some natural complexity classes are
incomparable is wrong?    

I hereby state

Computational Complexity Class Comparability Conjecture (C^5)

Most informal version: "There is really only one natural notion of 'hardness',
just as there seems to be only one natural notion of 'logical strength' ".

Semi-formal version: "All 'natural' positively defined complexity classes are
comparable under inclusion" ('positively defined' excludes the "co-" classes
like coNP but is irrelevant if you restrict your attention to deterministic
time and space complexity classes; an even stronger version of the conjecture
omits the words 'positively defined').

The semi-formal version implies a number of corollaries which can be precisely
stated formally, for example:

Formal corollary: "For any rational numbers q and r, DSPACE(n^q) and
DTIME(n^r) are comparable under inclusion"


The point is not that I believe this conjecture is true.  What I propose is
that we try to refute the conjecture by assuming it holds as broadly as we can
and seeing how much we can derive!  Either we reach a contradiction, in which
case we have an unprecedented type of result (an incomparability result in
complexity theory), or we obtain a whole new landscape.  In the former case we
can weaken the conjecture and continue the process; in the latter, if the new
structure is compelling enough we may get the insights needed to finally
separate P from PSPACE or NP.  (I don't think we can separate P from RP or BPP
because I think these complexity classes are identical, but that's a subject
for another time.)

Comments?

-- Joe Shipman