УДК 519.854.33 Alexander Antamoshkin, Igor Masich IDENTIFICATION OF PSEUDO-BOOLEAN FUNCTIONS PROPERTIES A method for identification of the algorithmically given pseudo-Boolean functions properties is suggested. <...> The method presupposes approximation of the functions by quadratic polynomials, that permits to associate the problem with one from the determined classes of problems. <...> INTRODUCTION Search optimization methods, i.e. optimization methods that don’t demand object functions and constraints are given by algebraic expressions (in an explicit form), are being developed in two main directions. <...> The first one is design and perfection of so-called adaptive search methods inclusive evolutionary and genetic algorithms, tabu search, simulated annealing etc. <...> These algorithms leave out of account properties of functions incoming in problem definition and so they allow solving arbitrary optimization problems. <...> The second direction is creation and investigation of search algorithms for specific problem classes. <...> Such algorithms must take into account properties of the chosen problem classes to the utmost. <...> That may be both exact algorithms and approximate ones, both regular ones and stochastic ones. <...> So classification of pseudo-Boolean functions has been carried out and the exact algorithms, including unimprovable ones, for solving arbitrary classes of unconstraint pseudo-Boolean optimization problems have been created in [1]. <...> The polynomial approximate algorithms for solving various classes of conditional pseudo-Boolean optimization problems have been created [2]. <...> When solving real-world problems with functions given by an algorithm in single particular cases, it is possible to identify the function properties starting from some a priori information. <...> But belonging of a function to any class is not obvious at all in many problems meeting in practice, so it is necessary to carry out identification of the function properties by means of realization of test steps. 1. <...> CLASSIFICATION OF PSEUDO-BOOLEAN FUNCTIONS Consider the following conditional pseudoBoolean optimization problem → ( ) max 2 j ( ) ≤ X Bn j , ∈ functions given by an algorithm (all functions or a part of them). where C( )X and A ( )Xj 66 Проблемы машиностроения и автоматизации, № 2 – 2007 A X H j m C X =1, , (1) are pseudo-Boolean represented as O ( )Xk <...>