zbMATH — the first resource for mathematics

Fuzzy relation equations. I: The general and specialized solving algorithms. (English) Zbl 1024.03520
Summary: 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.

03E72 Theory of fuzzy sets, etc.
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI