The definition of nearest-neighbor probability p(C) is introduced to characterize classification problems with binary inputs. It measures the likelihood that two patterns, which are close according to the Hamming distance, are assigned to the same class. It is shown that the generalization ability g NN (C) of neural networks that resemble the nearest-neighbor algorithm can be expressed as a function of p(C) and is upper bounded by p(C) when p(C) > 0:5. In the opposite case, a proper operator, called complementation, is proposed to improve the classification process in the test phase.