In the wake of Vinay Deolalikar's maybe proof that P != NP, I found myself thinking about the old P ?= NP question. I realized that while I know of a many problems that are NP complete, I don't know of any problems that are:
1. in NP
2. not known to be in P
3. not known to be NP-complete
Are there such "NP incomplete" problems? And has anyone proved that if P not equal to NP, such NP-incomplete problems must exist? It would be surprising if they didn't since the NP-complete problems are the hardest problems in NP. Without an NP-incomplete class, there would be a sudden jump from so-called "easy" (in P) to hardest (NP-complete).
