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/}
}
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/