Geodesic
On the generic existential theory of finite graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 1710-1714.

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

Finite graphs are the most important mathematical objects that are used for solving many practical problems of optimization, computer science, modeling. Many such problems can be formulated as problems related with solving systems of equations over graphs, which lead to the need for the development of algebraic geometry. Algebraic geometry over such objects is closely related to properties of existential theories. From a practical point of view, the most important questions concern decidability and computational complexity of these theories. Generic (existential) theory consists of all (existential) statements which are true for almost all graphs. Classical $0$-$1$ law for graphs implies that generic theory of finite graphs is decidable, while the classical elementary theory of graphs is undecidable. In this article we study the generic existential theory of finite graphs. We describe this theory as the set of all existential statements that are consistent with the theory of graphs. We prove that this theory is NP-complete. This means that there are no polynomial algorithms that recognize this theory, provided the inequality of classes $\text{P}$ and $\text{NP}$.
Keywords: graphs, generic theory. 
@article{SEMR_2020_17_a37,
     author = {A. N. Rybalov},
     title = {On the generic existential theory of finite graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {1710--1714},
     publisher = {mathdoc},
     volume = {17},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2020_17_a37/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On the generic existential theory of finite graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2020
SP  - 1710
EP  - 1714
VL  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2020_17_a37/
LA  - en
ID  - SEMR_2020_17_a37
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On the generic existential theory of finite graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2020
%P 1710-1714
%V 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2020_17_a37/
%G en
%F SEMR_2020_17_a37
A. N. Rybalov. On the generic existential theory of finite graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 17 (2020), pp. 1710-1714. http://geodesic.mathdoc.fr/item/SEMR_2020_17_a37/

[1] M. Garey, D. Johnson, Computers and Intractability, Freeman Co, San Francisco, 1979 | MR | Zbl

[2] Y.V. Glebsky, D.I. Kogan, M.I. Liogonky, V.A. Talanov, “Volume and fraction of satisfiability of formulas of the lower predicate calculus”, Kibernetika, 1969:2 (1969), 17–27 | MR

[3] E.Y. Daniyarova, A.G. Myasnikov, V.N. Remeslennikov, Algebraic geometry over algebraic structures, SB RAS, Novosibirsk, 2016 | MR

[4] I.A. Lavrov, “Effective inseparability of the set of identically true and finitely refutable formulas of some elementary theories”, Algebra logika, 2:1 (1963), 5–18 | MR | Zbl

[5] A.G. Myasnikov, V.N. Remeslennikov, “Generic theories as a method for approximating elementary theories”, Algebra Logika, 53:6 (2015), 512–519 | DOI | MR | Zbl