О сложности экзистенциальной и универсальной теорий конечных полей | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/9

Конечные поля являются важнейшими математическими объектами, которые используются при решении многих практически важных задач оптимизации, информатики, передачи информации и криптографии. Многие такие задачи можно формулировать как задачи, связанные с решением систем уравнений над полями, что приводит к необходимости развития алгебраической геометрии. Алгебраическая геометрия над этими объектами тесным образом связана со свойствами экзистенциальных и универсальных теорий. С практической точки зрения важнейшими являются вопросы разрешимости и вычислительной сложности этих теорий. В работе изучается вычислительная сложность экзистенциальной и универсальной теорий конечных полей. Доказывается, что экзистенциальная теория класса всех конечных полей является NP-трудной, а универсальная теория этого класса является co-NP-трудной. Это означает, что, при условии неравенства классов сложности P, NP и co-NP, не существует полиномиальных алгоритмов, распознающих эти теории.