More on NP-Incomplete Problems (Ladner's Theorem)

I did a bit of searching regarding my previous post, and it is known that if P != NP then there do exist NP Incomplete problems. They're actually called "NP Intermediate" rather than "NP Incomplete" problems. I like my name "NP Incomplete" better but the term "complete" may have a specific meaning that doesn't apply to the NP intermediate class --- I don't know.

The existence of NP incomplete problems was proved (assuming P != NP) by Richard Ladner in 1975. I haven't looked at it but hope to soon. Some well known problems thought to be NP Intermediate are:

1. Graph Isomorphism
2. Factoring

Garey and Johnson also mentions Linear Programming as a candidate for NP intermediate, but we now know that LP's are in P.  It's good to remember we are making progress.