On the relation between equations with max-product composition and the covering problem
Systems of equations with max-product composition are considered. It is shown that solving these equations is closely related with the covering problem, which belongs to the category of NP-hard problems. It is proved that minimal solutions of equations correspond to irredundant coverings. In terms of the covering problem the conditions of compatibility of equations, of redundancy of equations, of uniqueness of solution, of uniqueness of minimal solution are determined. Concepts of essential, non-essential, semi-essential and super-essential variables are suggested. Ways of simplification of a covering problem and methods of its solving are considered. (c) 2005 Elsevier B.V. All rights reserved.
max-product composition covering problem np-hard problems minimal solutions fuzzy relations fuzzy relation equations inverse problem np-complete problems