MRHS equation systems that can be solved in polynomial time
Zajac, Pavol
Tatra Mountains Mathematical Publications, Tome 65 (2016), / Harvested from Mathematical Institute
Link
Link

In this article we study the difficulty of solving Multiple Right-Hand Side (MRHS) equation systems. In the first part we show that in generalsolving 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 basedon decoding problems that can be solved in polynomial time.

Publié le : 2016-01-01
DOI : https://doi.org/10.2478/tatra.v67i0.449 
@article{449,
     title = {MRHS equation systems that can be solved in polynomial time},
     journal = {Tatra Mountains Mathematical Publications},
     volume = {65},
     year = {2016},
     doi = {10.2478/tatra.v67i0.449},
     language = {EN},
     url = {http://dml.mathdoc.fr/item/449}
}

Zajac, Pavol. MRHS equation systems that can be solved in polynomial time. Tatra Mountains Mathematical Publications, Tome 65 (2016) . doi : 10.2478/tatra.v67i0.449. http://gdmltest.u-ga.fr/item/449/