The complexity analysis of solving the max-product fuzzy relation equation with LU decomposition

摘要

L degrees U-factorization was recently used to solve the max-product fuzzy relation equation by Molai(Inf Sci 234:86-96, 2013). Considering the forward and backward substitutions play an important role in this method, this paper firstly amend the forward and backward substitutions for solving max-product fuzzy relation equation with L degrees U-factorization. And then, the computational complexities of improved forward and backward substitutions are analyzed in detail. Finally, we find that the L degrees U-factorization acts as splitting an irredundant covering of max-product fuzzy relation equation into two parts. It therefore cannot change the fact that finding the solutions of max-product fuzzy relation equation with L degrees U-factorization is an NP-hard problem. On the contrary, the computational expense will linearly increase with the number of minimal solutions of L degrees y=b.