Geodesic
Study of systems of equations over various classes of finite matroids
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 1094-1102.

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper, it is proved that the problem of checking compatibility of a finite system of equations over a matroid of rank not exeeding $k$ is $\mathcal{NP}$-complete for ${k \geqslant 2}$. Moreover, it is proved that the problem of checking compatibility of a finite system of equations over a $k$-uniform matroid is also $\mathcal{NP}$-complete for ${k \geqslant 2}$, and the problem of checking compatibility of a finite system of equations over a partition matroid of rank not exeeding $k$ is polynomially solvable for ${k=2}$ and $\mathcal{NP}$-complete for ${k \geqslant 3}$.
Keywords: graph, matroid, system of equations, computational complexity. 
@article{SEMR_2022_19_2_a16,
     author = {A. V. Ilev},
     title = {Study of systems of equations over various classes of finite matroids},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1094--1102},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a16/}
}
TY  - JOUR
AU  - A. V. Ilev
TI  - Study of systems of equations over various classes of finite matroids
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 1094
EP  - 1102
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a16/
LA  - ru
ID  - SEMR_2022_19_2_a16
ER  - 
%0 Journal Article
%A A. V. Ilev
%T Study of systems of equations over various classes of finite matroids
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 1094-1102
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a16/
%G ru
%F SEMR_2022_19_2_a16
A. V. Ilev. Study of systems of equations over various classes of finite matroids. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 1094-1102. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a16/

[1] Y.V. Matiyasevich, “Enumerable sets are diophantine”, Sov. Math., Dokl., 11 (1970), 354–358 | MR | Zbl

[2] E.W. Mayr, A.R. Meyer, “The complexity of the word problems for commutative semigroups and polynomial ideals”, Adv. Math., 46:3 (1982), 305–329 | DOI | MR | Zbl

[3] S.A. Cook, “The complexity of theorem-proving procedures”, Proc. 3rd ann. ACM Sympos. Theory Computing (Shaker Heights, Ohio, 1971), ACM, 1971, 151–158 | DOI | Zbl

[4] E.Y. Daniyarova, A.G. Myasnikov, V.N. Remeslennikov, “Algebraic geometry over algebraic structures”, Algebra Logic, 57:6 (2019), 414–428 | DOI | MR | Zbl

[5] A.Y. Nikitin, A.N. Rybalov, “On complexity of the satisfiability problem of systems over finite posets”, Prikl. Diskretn. Mat., 39 (2018), 94–98 | DOI | MR | Zbl

[6] A.N. Rybalov, “On complexity of the existential and universal theories of finite fields”, Prikl. Diskretn. Mat., 45 (2019), 85–89 | DOI | MR | Zbl

[7] A.V. Ilev, “Decidability of universal theories and axiomatizability of hereditary classes of graphs”, Trudy Inst. Mat. i Mekh. UrO RAN, 22, no. 1, 2016, 100–111 | MR

[8] A.V. Ilev, V.N. Remeslennikov, “Study of the compatibility of systems of equations over graphs and finding their general solutions”, Vestnik Omskogo Universiteta, 4(86) (2017), 26–32

[9] A.V. Il'ev, V.P. Il'ev, “Algorithms for solving systems of equations over various classes of finite graphs”, Prikl. Diskretn. Mat., 53 (2021), 89–102 | DOI | MR | Zbl

[10] A.V. Iliev, “On axiomatizability of hereditary classes of graphs and matroids”, Sib. Èlectron. Mat. Izv., 13 (2016), 137–147 | MR | Zbl

[11] A.V. Il'ev, V.P. Il'ev, “On axiomatizability and decidability of universal theories of hereditary classes of matroids”, J. Physics: Conf. Ser., 2019, 012056 | DOI

[12] A.V. Il'ev, V.P. Il'ev, “On axiomatizability of the class of finitary matroids and decidability of their universal theory”, Sib. Èlectron. Mat. Izv., 17 (2020), 1730–1740 | DOI | MR | Zbl

[13] H. Whitney, “On the abstract properties of linear dependence”, Am. J. Math., 57 (1935), 509–533 | DOI | MR | Zbl

[14] M.R. Garey, D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman and Co, San Francisco, 1979 | MR | Zbl