Во многих практических ситуациях необходимо вычислять внешнюю оценку для области значений алгебраического полинома от нескольких переменных на заданных интервалах с определённой относительной погрешностью ε > 0. Известно, что эта задача является NP-трудной для всех ε < 1/8, но не было известно, является ли задача NP-трудной для других значений ε. В работе даётся полный ответ на этот вопрос, а именно, доказано, что рассматриваемая задача является NP-трудной для всех ε ≤ 1 и полиномиально разрешима для всех ε > 1.  

 

Семинар пройдёт в смешанном формате: очное заседание пройдёт в конференц-зале ФИЦ ИВТ (к.513), онлайн подключение будет осуществляться по ссылке: https://vcs-6.ict.nsc.ru/rooms/gus-s1x-jdx-7cn/join