The problems of discrete optimization are of importance in a number of applications. One of the various problems of discrete minimization with special constraints, not previously considered, is formulated. A complexity degree of the assigned problem is studied from the viewpoint of algorithm theory. Non–deterministically polynomial (NP)–compleleness of the discrete minimization problem is shown. The algorithms proposed for the solution of a frequently occurring special case of the problem have polynomial time complexity and their set is a finite polynomial approximated scheme.