EN|RU

Том 19, номер 6, 2012 г., Стр. 56-71

УДК 519.87+519.854
Плясунов А. В., Панин А. В.
Задача ценообразования. Часть 2. Вычислительная сложность

Аннотация:
Показано, что исследуемая задача принадлежит классу Log-APX, не может быть аппроксимируема с абсолютной погрешностью, ограниченной константой, и связанная с ней задача оценивания нетривиальна в классе $\Delta^p_2$. Приведены два полиномиально разрешимых случая задачи.
Библиогр. 8.

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

Плясунов Александр Владимирович 1,2
Панин Артём Александрович 1,2

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: apljas@math.nsc.ru, arteam1897@gmail.com

Статья поступила 1 июня 2011 г.
Исправленный вариант — 4 июня 2012 г.

 © Институт математики им. С. Л. Соболева, 2015