[tradedash]

That's not my understanding of the NP domain. Take Prime Factorization for example. Which isn't even NP-complete, or Sudoku which is NP-complete. Both of these problems can be made really hard by changing 1 small variable, size.

Edit: I understand that your argument is about the average case and not the worst case.

[adrianN]

If you pick a random number the chances are really good that it has many small factors and hence is a lot easier to factorize than its number of bits might suggest. Half of all numbers are divisible by two, two thirds of all numbers are divisible by two or three.

Regarding Sudoku, my hunch is that there is a critical density of numbers where random problems are harder than average. That's the case for SAT, there is a phase transition on the number of variables per clause where above a critical value almost all instances are not satisfiable and below the threshold almost all instances are. Instances right at the threshold tend to be hard for our current solvers.