Geodesic
On complexity of the existential and universal theories of finite fields
Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 85-89.

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

Finite fields are the most important mathematical objects that are used for solving many practical problems of optimization, computer science, information transfer and cryptography. Many such problems can be formulated as problems connected with the solving systems of equations over fields. This leads to the need for the development of algebraic geometry. Algebraic geometry over such objects is closely related to properties of existential and universal 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 and universal theories of finite fields. We prove that the existential theory of finite fields is NP-hard, and the universal theory of finite fields is co-NP-hard. This means that there are no polynomial algorithms that recognize these theories, provided the inequality of classes P, NP and co-NP.
Keywords: finite fields, universal theory, existential theory, NP-hardness. 
@article{PDM_2019_3_a9,
     author = {A. N. Rybalov},
     title = {On complexity of the existential and universal theories of finite fields},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {85--89},
     publisher = {mathdoc},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_3_a9/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On complexity of the existential and universal theories of finite fields
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 85
EP  - 89
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_3_a9/
LA  - ru
ID  - PDM_2019_3_a9
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On complexity of the existential and universal theories of finite fields
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 85-89
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_3_a9/
%G ru
%F PDM_2019_3_a9
A. N. Rybalov. On complexity of the existential and universal theories of finite fields. Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 85-89. http://geodesic.mathdoc.fr/item/PDM_2019_3_a9/

[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] Garey M., Johnson D., Computers and Intractability, Freeman Co, N. Y., 1979, 340 pp.

[3] Ax J., “The elementary theory of finite fields”, Ann. Math., 88:2 (1968), 239–271 | DOI | MR | Zbl