Дата публикации: 2019

Дата публикации в реестре: 2020-03-03T19:13:07Z

Аннотация:

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

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2019. № 45. С. 85-89