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