Мне повлиял необычайный взрыв в сглаженном анализе, и меня поразило утверждение в статье « Сглаженный анализ целочисленного программирования» . Это говорит о том, что целочисленное линейное программирование находится в сглаженном P, если оно ограничено полиномами. Это было существенно верно в силу того, что целочисленное программирование является псевдополиномиальным!
Поэтому вопрос таков:
Относится ли это к другим проблемам повсеместно? В частности, каковы ограничения?
Ответы:
Целочисленное программирование строго NP-сложно, поэтому целочисленные программы вообще не могут быть решены за псевдополиномиальное время. Результат Рёглина и Вёкинга заключается в том, что при условии, что диапазон целых чисел, которые могут принимать переменные, ограничен полиномиальным образом (рандомизированная) псевдополиномиальная разрешимость эквивалентна полиномиальной сглаженной сложности. Таким образом, общие целочисленные программы не имеют полиномиальной сглаженной сложности.
Утверждение «рандомизированная псевдополиномиальная сложность = полиномиальная сглаженная сложность» в общем случае не соответствует действительности. Например, эвристика переворота для Max-Cut выполняется за псевдополиномиальное время, но неизвестно, может ли быть найден локальный оптимум по сравнению с эвристикой переворота с полиномиальной сглаженной сложностью (ср. Etscheid and Röglin, SODA 2014).
источник