Оценивание на интервале области значений полинома с относительной погрешностью ε

Оценивание области значений полинома с относительной погрешностью ε на интервале является NP-трудным при ε 1 и полиномиально сложным при ε 1 Крейнович Владислав Яковлевич Университет Техаса в Эль-Пасо США Шарый Сергей Петрович ФИЦ ИВТ Новосибирск Россия Во многих практических ситуациях необходимо вычислять интервальную оценку для области значений полинома от нескольких переменных на заданных интервалах с определённой относительной погрешностью ε.
В 1981 году А.А.Гагановым было установлено что эта задача является труднорешаемой NP-трудной для всех ε 18 но до сих пор не было известно является ли задача NP-трудной для других значений ε.
В представляемой работе даётся полный ответ на этот вопрос а именно показано что рассматриваемая задача является NP-трудной для всех ε 1 и полиномиально разрешима для всех ε 1. Слайды:

Источник: rutube.ru