Исследование систем уравнений над различными классами конечных матроидов

Аннотация

В работе доказано, что задача проверки совместности конечной системы уравнений над матроидом ранга, не превосходящего $k$, является $\mathcal{NP}$-полной задачей при $k \geqslant 2$.

Кроме того, доказано, что задача проверки совместности конечной системы уравнений над $k$-однородным матроидом также $\mathcal{NP}$-полна при $k \geqslant 2$, и задача проверки совместности конечной системы уравнений над матроидом разбиения ранга, не превосходящего $k$, полиномиально разрешима при $k = 2$ и $\mathcal{NP}$-полна при $k \geqslant 3$.