MRHS equation systems that can be solved in polynomial time

Abstract

In this article we study the difficulty of solving Multiple Right-
Hand Side (MRHS) equation systems. In the first part we show that in general
solving MRHS systems is NP-hard. In the next part we focus on special (large)
families of MRHS systems that can be solved in polynomial time with two algorithms:
one based on linearization of MRHS equations, and the second one based
on decoding problems that can be solved in polynomial time.