On the generic existential theory of finite graphs

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 P and NP.