Fuzzy relation equations. I: The general and specialized solving algorithms.

*(English)*Zbl 1024.03520Summary: In this article, we develop a new method and an algorithm to solve a system of fuzzy relation equations. We first introduce a solution-base-matrix and then give a tractable logical representation of all minimal solutions. Next, we design a new universal algorithm to get them. Two simplification rules are found to simplify the solution-base-matrix. We show that a polynomial time algorithm to find all minimal solutions for a general system of fuzzy relation equations simply does not exist unless \(\text{P}=\text{NP}\). Hence, the problem of solving fuzzy relation equations is an NP-hard problem in terms of computational complexity. Our universal algorithm is still useful when one does not solve a large number of equations. In many real applications, the problem of solving fuzzy relation equations can be simplified into polynomial time problems. In this article, we discuss several cases of practical applications which have such polynomial algorithms.