On generic complexity of the existential theories

A. N. Rybalov

Prikladnaâ diskretnaâ matematika, no. 3 (2020), pp. 120-126

Résumé

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.

Détail

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