On complexity of the existential and universal theories of finite fields | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/9

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.