There are thousands of natural PC problems. Assuming P NE NP how many natural problems are there that are
in NP-P but are NOT NPC? Some candidates are Factoring, Discrete Log, Graph Isom, some in group theory, and any natural sparse set. See
here for some more.
A student asked me WHY there are so few natural intermediary problems. I don't know but here are some
- Bill you moron, there are MANY such problems. You didn't mention THESE problems (Followed by a list of problems
that few people have heard of but seem to be intermediary.)
- This is a question of Philosophy and hence not interesting.
- This is a question of Philosophy and hence very interesting.
- That's just the way it goes.
- By Murphy's law there will be many problems that we can't solve quickly.
At least in complexity theory there are SOME candidates for intermediary sets.
In computability theory, where we know Sigma_1 \ne \Sigma_0, there are no
candidates for natural problems that are c.e., not decidable, but not complete. There have been some attempts to show that there can't be any
such sets, but its hard to define ``natural'' rigorously. (There ARE sets that are c.e., not dec, not complete, but they are
constructed for the sole purpose of being there. My darling would call them `dumb ass' sets,
a terminology that my class now uses as well.)
A long time ago an AI student was working on classifying various problems in planning. There was one that was c.e. and not decidable
and he was unable to show it was complete. He asked me to help him prove it was not complete. I told him, without looking at it,
that it was COMPLETE!!!!!!!!! My confidence inspired him to prove it was complete.
So, aside from the answers above, is there a MATH reason why there are so few
intermediary problems in Complexity, and NONE in computability theory?
Is there some other kind of reason?