Geodesic
On generic complexity of the existential theories
Prikladnaâ diskretnaâ matematika, no. 3 (2020), pp. 120-126.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\text{NP}$-hard. We prove that under the conditions $\text {P} \neq \text{NP}$ and $\text{P} = \text{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. 
@article{PDM_2020_3_a8,
     author = {A. N. Rybalov},
     title = {On generic complexity of the existential theories},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {120--126},
     publisher = {mathdoc},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_3_a8/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On generic complexity of the existential theories
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 120
EP  - 126
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_3_a8/
LA  - ru
ID  - PDM_2020_3_a8
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On generic complexity of the existential theories
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 120-126
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2020_3_a8/
%G ru
%F PDM_2020_3_a8
A. N. Rybalov. On generic complexity of the existential theories. Prikladnaâ diskretnaâ matematika, no. 3 (2020), pp. 120-126. http://geodesic.mathdoc.fr/item/PDM_2020_3_a8/

[1] Daniyarova E. Y., Myasnikov A. G., Remeslennikov V. N., Algebraic Geometry over Algebraic Structures, SB RAS Publ., Novosibirsk, 2016, 288 pp. (in Russian)

[2] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[3] Garey M., Johnson D., Computers and Intractability, Freeman Co, N. Y., 1979, 340 pp. | MR | Zbl

[4] Impagliazzo R., Wigderson A., “P $=$ BPP unless E has subexponential circuits: Derandomizing the XOR Lemma”, Proc. 29th STOC, ACM, El Paso, 1997, 220–229 | MR

[5] Knuth D. E., The Art of Computer Programming, Addison-Wesley, Reading, Massachusetts, 1997 | MR

[6] Rybalov A., “On generic complexity of the validity problem for Boolean formulas”, Prikladnaya Diskretnaya Matematika, 2016, no. 2(32), 119–126 (in Russian)