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

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