Several classes of polynomial-time solvable fuzzy relational inequalities

摘要

Finding the list of all minimal solutions of a fuzzy relational system is a tough work. Actually it has been proved to be NP hard recently by Markovskii. (A.V. Markovskii, On the relation between equations with max-product composition and the covering problem. Fuzzy Sets Systems 153, pp. 261–273, 2005). However, practical programs for solving these problems usually run much faster than they are supposed to be in theoretical result. This motivates us to ask: are there any polynomial-time solvable fuzzy relation systems and what kind of systems they should be? This paper devotes to answering this question by analyzing the computational complexity of a proposed algorithm for solving fuzzy relation systems. It is proved that a fuzzy relation system has polynomial time algorithm whenever it has poly(m, n) many quasi-minimal solutions, where m×n is its dimension. Based on the conclusion, some conditions are proposed, under which fuzzy relation systems can be solved in polynomial time. Presented examples show the practicality of these conditions.