Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports]
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports], 2020, Volume 17, Pages 1710–1714
DOI: https://doi.org/10.33048/semi.2020.17.115
(Mi semr1309)
 

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
References:
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.
Funding agency Grant number
Russian Science Foundation 19-11-00209
This research was supported by Russian Science Foundation (grant № 19-11-00209.)
Received November 20, 2019, published October 23, 2020
Bibliographic databases:
Document Type: Article
UDC: 510.652
MSC: 11U99
Language: English
Citation: A. N. Rybalov, “On the generic existential theory of finite graphs”, Sib. Èlektron. Mat. Izv., 17 (2020), 1710–1714
Citation in format AMSBIB
\Bibitem{Ryb20}
\by A.~N.~Rybalov
\paper On the generic existential theory of finite graphs
\jour Sib. \`Elektron. Mat. Izv.
\yr 2020
\vol 17
\pages 1710--1714
\mathnet{http://mi.mathnet.ru/semr1309}
\crossref{https://doi.org/10.33048/semi.2020.17.115}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000583296500001}
Linking options:
  • https://www.mathnet.ru/eng/semr1309
  • https://www.mathnet.ru/eng/semr/v17/p1710
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:176
    Full-text PDF :135
    References:19
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024