This seems like a definition issue, with respect to the set from which we are randomly sampling... what constitutes the problem? If you randomly select numbers and try to factor them--which to me seems like a fair way to define the problem: factoring, not two-primes factoring--the vast majority of numbers are, in fact, very easy to factor ;P. Instead, we say we only want to randomly select a number which is only two primes multiplied together in order to find the juicy hard versions of the problem. (And, even then, finding those numbers isn't precise! We rely on probabilistic primarily tests to weed out numbers that are probably not prime.)<p>Similarly, who is to say that there isn't some way to define what the hard instances of NP-complete problems are, and we just should be sampling from that difficult region of the problem space instead of all possible problems, the same way we sample only from the difficult-to-factor coprimes instead of from all possible numbers? There is definitely something interesting going on with the harder instances of these problems, and researchers have managed to discover a kind of "phase transition" among instances of some of the problems between ones with so many solutions they are easy and ones with so few solutions they are also once again easy (and my knowledge on this is about 20 years rusty and outdated... maybe this is better understood and characterized now).