From: hbe@sonia.math.ucla.edu (H. Enderton)
Newsgroups: sci.logic,sci.math
Subject: Re: [Q] BUILDING LARGE SNAKES
Date: 10 May 1998 16:10:50 GMT

Yann DAVID  <100552.1400@CompuServe.COM> wrote:
>[BTW: is there any problem that cannot be decided by a TM, but is not
> as hard as (not equivalent to) the halting problem at the same time?

Yes.  This was "Post's Problem."  In 1957 Friedberg and Muchnik
(independently) showed the existence of "intermediate" problems
(degrees).

> Like if P#NP, then there must exist problems in NP that cannot be solved
> in polynomial time, while not being NP-complete.]

Well, the analogy may not be perfect!

--Herb Enderton
  hbe@math.ucla.edu