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.
Fangfang Guo Yonghong Ren
School of Mathematical Sciences Dalian University of Technology Dalian,Liaoning 116024,China School of Mathematics Liaoning Normal University Dalian,Liaoning 116029,China
国际会议
厦门
英文
36-41
2014-08-19（万方平台首次上网日期，不代表论文的发表时间）