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.