FOM: Intermediate degrees, CH, and P=NP

[Joe Shipman]

Calhoun:

>It seems to me that the lack of specific natural examples of c.e. sets
>with intermediate Turing degree is a special case of a broader
phenomenon.

>It seems that our main tool for separating levels of hierarchies is by
>variations on Cantor diagonalization, including "fancy" variations such
as
>priority arguments and forcing.  Simple diagonlization produces natural

>examples (the halting set, the continuum), fancy diagonalization is
>required to produce the "unnatural" intermediate sets.  (Such as the
sets
>of cardinality between Aleph_0 and c that can be constructed in models
of
>ZFC by forcing.)

An excellent point.  One place the analogy fails (at least if you accept
AC) is that cardinals are linearly ordered and degrees are not.

>Godel was interested in the analogy between Post's problem and the
>Continuum Problem (according to an earlier posting by Martin Davis).  I

>think there is another interesting analogy between Post's problem and
the
>complexity theory problem of finding a set intermediate between EXPTIME

>and P.
>A simple diagonalization separates EXPTIME from P, but (as far as I
know)
>no set has yet been shown to be intermediate between them, despite a
huge
>collection of natural candidates (e.g. the NP-Complete sets).  And
oracle
>results suggest that NP cannot be separated from P by any known form of

>diagonalization.

Another excellent point.  The problem is there is a limit to how fancy
P-time diagonalizations can be.  By the way, the same remarks could
apply to separating LOGSPACE and PSPACE wirh logspace reductions, as
apply to separating P and EXPTIME with P-time reductions.  The third
analogy, between P=NP and CH, has been discussed on the F.O.M. list
before (I suppose Aleph_1 could be analogous to SAT, but it would be
shocking if P=NP or NP=EXPTIME were undecidable).

A big question is which formal analogy to pursue, because we know there
are serious structural differences between Post's problem and the
Continuum problem (cardinalities are well-ordered, degrees are not even
linearly ordered).  Are the "P-time degrees" linearly ordered?  Probably
not, but the "natural" P-time degrees may well be (and I suspect if
there are any "natural" intermediate c.e. degrees they are also linearly
ordered).  A while back I proposed a "Computational Complexity Class
Comparability Conjecture", which informally says that all "natural"
complexity classes are linearly ordered and can be partially formalized
in various ways.  Steve Cook suggested a potential counterexample of
logsquared space vs. polynomial time (group isomorphism, where the
groups are given by their multiplication tables, is in the former class
while the circuit value problem is in the latter class, and he thought
neither was in the other class).

We should pursue these analogies further!  Here is one remark to start:
it is AC which tames cardinalities so that they must be linearly
ordered; what kind of analogy for this can we come up with in the worlds
of c.e. degrees and P-time degrees?

-- Joe Shipman