MRHS equation systems that can be solved in polynomial time

Pavol Zajac

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.

Full Text:

 Subscribers Only


DOI: https://doi.org/10.2478/tatra.v67i0.449