  We introduce the notion of a stable instance for a discrete optimization
problem, and argue that in many practical situations only sufficiently stable
instances are of interest. The question then arises whether stable instances of
NP--hard problems are easier to solve. In particular, whether there exist
algorithms that solve correctly and in polynomial time all sufficiently stable
instances of some NP--hard problem. The paper focuses on the Max--Cut problem,
for which we show that this is indeed the case.
