Hits:

Indexed by:会议论文

Date of Publication:2014-08-19

Included Journals:EI、CPCI-S、SCIE

Page Number:36-41

Abstract: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 mxn 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.