On the Complexity of Matroid Isomorphism Problem

Raghavendra Rao B. V., Jayalal M. N. Sarma

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in ${\Sigma }_2^p$. In the case of linear matroids, which are represented over pol…