"Записки научных семинаров ПОМИ"

Том 507, стр. 140-156

С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, наб. р. Фонтанки 27 191023 С.-Петербург, Россия

alch@pdmi.ras.ru

Аннотация: Рассмотрим систему полиномиальных уравнений от $n$ неизвестных степени не больше $d$ с множеством всех общих нулей $V$. Мы предлагаем субэкспоненциальные алгоритмы (в общем случае и в случае нулевой характеристики) для построения $n+1$ уравнений степени не больше $d$, задающих алгебраическое многообразие $V$. Далее, мы строим $n$ уравнений, задающих $V$, и устанавливаем явную оценку на их степени. Она дважды экспоненциальна от $n$. Время работы алгоритма для построения этих $n$ уравнений также дважды экспоненциально от $n$. Библ. -- 11 назв.
Ключевые слова:алгебраические многообразия, эффективные алгоритмы, задающие уравнения, число уравнений [algebraic varieties, effective algorithms, defining equations, number of equations]