|
Mathematical logic, algebra and number theory
On the generic existential theory of finite graphs
A. N. Rybalovab a Omsk State Technical University, 11, Mira ave., Omsk, 644050, Russia
b Sobolev Institute of Mathematics, 13, Pevtsova str., Omsk, 644043, Russia
Abstract:
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.
Received November 20, 2019, published October 23, 2020
Citation:
A. N. Rybalov, “On the generic existential theory of finite graphs”, Sib. Èlektron. Mat. Izv., 17 (2020), 1710–1714
Linking options:
https://www.mathnet.ru/eng/semr1309 https://www.mathnet.ru/eng/semr/v17/p1710
|
Statistics & downloads: |
Abstract page: | 176 | Full-text PDF : | 135 | References: | 19 |
|