Полиномиальное приближение времени на рюкзак

Question

knapsack problem можно решить в O(n²V), где V = max(v[i], i = 1,..,n) обозначает максимальное значение любого элемента. Если мы «сменим единицы» параметром округления θ = ε/n * V и рассмотрим измененные значения y[i] = ceil(v[i]/θ), мы получим время работы O(n³/ε) для любого фиксированногоε > 0.

В книге Алгоритм проектирования по Джон Клейнбергом, они заявляют:

Зависимость от требуемой точности ε не многочленом, так как время работы включает в себя 1/ε, а не log 1/ε.

Прежде всего, вся идея термина псевдо-полином не совсем ясно для меня, несмотря на то, что я читал несколько статей о нем. Однако, помимо этого пробела в знаниях, я в основном спрашиваю себя, почему зависимость от ε будет полиномиальной, если время работы будет включать log 1/ε вместо 1/ε.

Answer 1

Независимо от того, является ли проблема полиномиальным временем или нет, зависит от того, как кодируются его экземпляры. Например, я могу определить проблему PADDED-SATISFIABILITY, действительные экземпляры которой состоят из булевой формулы с n переменными, за которой следуют 2^n младших бит. Благодаря дополнению, PADDED-SATISFIABILITY разрешима в полиномиальное время (в отличие, по-видимому, SATISFIABILITY, NP-hard).

Когда экземпляры включают целые числа, принято предполагать кодировку, в которой количество битов, используемых для представления положительного целого числа, составляет около log2 этого целого числа. A алгоритм псевдополиномиального времени, в этом контексте означает, что если мы перейдем от двоичного представления положительных целых чисел к унарным, так что они должны экспоненциально (!) Отображать больше битов, то алгоритм является полиномиально- время.

Если мы сделаем (частое) предположение о том, что 1/ε является положительным целым числом, то Клейнберг указывает, что полиномиальная зависимость будет на log 1/ε, так как это примерно число бит, требуемое для указания того, что параметр в двоичном формате. Количество бит в унарном представлении будет приблизительно 1/ε.