Prikladnaya Diskretnaya Matematika
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



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Prikl. Diskr. Mat., 2020, Number 49, Pages 120–126 (Mi pdm718)  

This article is cited in 1 scientific paper (total in 1 paper)

Mathematical Backgrounds of Informatics and Programming

On generic complexity of the existential theories

A. N. Rybalov

Sobolev Institute of Mathematics, Omsk, Russia

Abstract: Many problems about finite graphs and finite fields can be formulated in the universal algebraic geometry, where these objects are considered as algebraic structures in the given language. Algebraic geometry over such objects is closely related to properties of existential theories. From a practical point of view, the most important are questions about decidability and computational complexity of these theories. In this paper we study the computational complexity of existential theories of algebraic structures of finite predicate language. It is known that the existential theory of any algebraic structure with more than one element is $NP$-hard. We prove that under the conditions $\text {P} \neq NP$ and $P = BPP$, for this theories there is no polynomial strongly generic algorithm. To prove this theorem we use the method of generic amplification, which allows to construct generically undecidable problems from the problems undecidable in the classical sense. The main ingredient of this method is a technique of cloning, which unites inputs of the problem together in the large enough sets of equivalent inputs. Equivalence is understood in the sense that the problem is solved similarly for them.

Keywords: generic complexity, finite algebraic structure, existential theory.

Funding Agency Grant Number
Russian Science Foundation 19-11-00209


DOI: https://doi.org/10.17223/20710410/49/9

Full text: PDF file (631 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 510.52

Citation: A. N. Rybalov, “On generic complexity of the existential theories”, Prikl. Diskr. Mat., 2020, no. 49, 120–126

Citation in format AMSBIB
\Bibitem{Ryb20}
\by A.~N.~Rybalov
\paper On generic complexity of the existential theories
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 49
\pages 120--126
\mathnet{http://mi.mathnet.ru/pdm718}
\crossref{https://doi.org/10.17223/20710410/49/9}


Linking options:
  • http://mi.mathnet.ru/eng/pdm718
  • http://mi.mathnet.ru/eng/pdm/y2020/i3/p120

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. V. Seliverstov, “Dvoichnye resheniya dlya bolshikh sistem lineinykh uravnenii”, PDM, 2021, no. 52, 5–15  mathnet  crossref
  • Прикладная дискретная математика
    Number of views:
    This page:36
    Full text:13
    References:4

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021