О генерической экзистенциальной теории конечных графов
Ключевые слова:
графы, генерическая теория.Аннотация
Конечные графы являются важнейшими математическими объектами, используемыми для решения многих практических проблем оптимизации,
информатики и моделирования. Такие проблемы часто могут быть связаны с решением систем уравнений в графах, что требует развития алгебраической геометрии. Алгебраическая геометрия над такими объектами тесно связана с изучением экзистенциальных теорий. Наиболее важными, с точки зрения приложений, являются вопросы о разрешимости и вычислительной сложности этих теорий. Генерическая (экзистенциальная) теория состоит из всех (экзистенциальных) предложений, истинных для почти всех графов. Из классического 0-1 закона для графов следует, что генерическая теория конечных графов разрешима, в то время как классическая элементарная теория неразрешима. В данной работе изучается генерическая экзистенциальная теория конечных графов. Доказывается, что она совпадает с множеством всех экзистенциальных
предложений, совместных с теорией графов. Также устанавливается ее NP-полнота.
