The property of a problem of being NP-complete means only that there are some instances of the problem that are hard to solve (unless, of course, P = N P ). It leaves open the possibility that such instances are uncommon and that, from a practical point of view, the problem is easy. The theory of average-case NP-completeness that has emerged in the last decade is meant to find more convincing examples of hard problems. The list of problems known to be NP-complete on average is still short. The paper adds a natural and important problem to this list--the word problem for finitely presented groups when the rewriting rules can be applied a bounded number of times. Besides proving the main result, the paper contains a thorough and informative introduction to˘ the theory of average-case complexity.