Оценивание на интервале области значений полинома с относительной погрешностью $\varepsilon$ является NP-трудным при $\varepsilon\leqslant 1$ и полиномиально сложным при $\varepsilon>1$

В. Крейнович^a, С. П. Шарый<sup>b

a</sup> University of Texas at El Paso, TX 79968, El Paso, USA
^b Федеральный исследовательский центр информационных и вычислительных технологий, Новосибирск, Россия

Аннотация: Во многих практических ситуациях необходимо вычислять внешнюю оценку для области значений полинома от нескольких переменных $f(x_1,\dots,x_n)$ на заданных интервалах $[\underline{x}_1,\overline{x}_1],\dots,[\underline{x}_n,\overline{x}_n]$ с определённой относительной погрешностью $\varepsilon>0$. Известно, что эта задача является NP-трудной для всех $\varepsilon < 1/8$, но не было известно, является ли задача NP-трудной для других значений $\varepsilon$. В нашей статье даётся полный ответ на этот вопрос, а именно, мы доказываем, что рассматриваемая задача является NP-трудной для всех $\varepsilon\leqslant1$ и полиномиально разрешима для всех $\varepsilon>1$.

Ключевые слова: интервал, полином, область значений, NP-трудная задача, полиномиально сложная задача, теорема Гаганова.

УДК: 519.6

Статья поступила: 01.08.2024
Переработанный вариант: 28.08.2024

DOI: 10.15372/SJNM20250305