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

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

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} 

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

 SHARE:

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
•  Number of views: This page: 36 Full text: 13 References: 4