О сложности экзистенциальной и универсальной теорий конечных полей

doi:10.17223/20710410/45/9

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О сложности экзистенциальной и универсальной теорий конечных полей	583 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/45/9

#конечные поля

#теория универсальности

#алгебраическая геометрия

#экзистенциальная теория

#NP-задачи

Title: О сложности экзистенциальной и универсальной теорий конечных полей
Title: On complexity of the existential and universal theories of finite fields
Creator: Рыбалов, Александр Николаевич
Date: 2019
DOI: 10.17223/20710410/45/9
Description: Конечные поля являются важнейшими математическими объектами, которые используются при решении многих практически важных задач оптимизации, информатики, передачи информации и криптографии. Многие такие задачи можно формулировать как задачи, связанные с решением систем уравнений над полями, что приводит к необходимости развития алгебраической геометрии. Алгебраическая геометрия над этими объектами тесным образом связана со свойствами экзистенциальных и универсальных теорий. С практической точки зрения важнейшими являются вопросы разрешимости и вычислительной сложности этих теорий. В работе изучается вычислительная сложность экзистенциальной и универсальной теорий конечных полей. Доказывается, что экзистенциальная теория класса всех конечных полей является NP-трудной, а универсальная теория этого класса является co-NP-трудной. Это означает, что, при условии неравенства классов сложности P, NP и co NP, не существует полиномиальных алгоритмов, распознающих эти теории.