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

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