|
This article is cited in 2 scientific papers (total in 2 papers)
Mathematical Backgrounds of Informatics and Programming
On complexity of the existential and universal theories of finite fields
A. N. Rybalov Sobolev Institute of Mathematics, Omsk, Russia
Abstract:
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.
Citation:
A. N. Rybalov, “On complexity of the existential and universal theories of finite fields”, Prikl. Diskr. Mat., 2019, no. 45, 85–89
Linking options:
https://www.mathnet.ru/eng/pdm674 https://www.mathnet.ru/eng/pdm/y2019/i3/p85
|
Statistics & downloads: |
Abstract page: | 193 | Full-text PDF : | 74 | References: | 27 |
|