Почему проблема ранца является псевдополиномом?

Question

Я знаю, что Knapsack является NP-полным, хотя его можно решить с помощью DP. Они говорят, что решение DP является pseudo-polynomial, поскольку оно экспоненциально по «длине ввода» (то есть количеству битов, необходимых для кодирования ввода). К сожалению, я не получил это. Кто-нибудь может объяснить, что pseudo-polynomial вещь для меня медленно?

Answer 1

Время выполнения равно O (NW) для неограниченной задачи о ранце с N предметами и ранцем размера W. Хотя W не является полиномиальным по длине ввода, что делает его псевдо полином.

Рассмотрим W = 1 000 000 000 000. Для представления этого числа требуется всего 40 бит, поэтому размер ввода = 40, но в вычислительной среде используется коэффициент 1 000 000 000 000, который равен O (2 ⁴⁰ ).

Таким образом, время выполнения более точно называется O (N.2 ^{бит в W} ), что является экспоненциальным.

Также см .:

• Как понять, что проблема с рюкзаком является NP-полной?
• NP-комплектность рюкзака
• Сложность алгоритма динамического программирования для задачи о ранце 0-1
• Псевдополиномиальное время

Answer 2

В большинстве наших проблем мы имеем дело с большими списками чисел, которые удобно вписываются в стандартные типы данных int / float. Из-за того, что большинство процессоров построены так, чтобы обрабатывать 4-8-байтовые числа за раз без дополнительных затрат (по сравнению с числами, которые умещаются, скажем, в 1 байт), мы редко сталкиваемся с изменением времени выполнения от увеличения наших чисел или в пределах диапазонов, с которыми мы сталкиваемся в реальных проблемах - поэтому доминирующим фактором остается только огромное количество точек данных, n или m факторов, к которым мы привыкли.

(Вы можете себе представить, что нотация Big-O скрывает постоянный коэффициент, который делит 32 или 64 бита на элемент данных, оставляя только количество точек данных, когда каждое из наших чисел вписывается в такое количество бит или меньше)

Но попробуйте переработать другие алгоритмы, чтобы воздействовать на наборы данных, включающие большие целые числа - числа, для представления которых требуется более 8 байтов, - и посмотрите, как это повлияет на среду выполнения. Величина используемых чисел всегда имеет значение, даже в других алгоритмах, таких как двоичная сортировка, когда вы выходите за пределы буфера безопасности, обычные процессоры дают нам «бесплатно», обрабатывая пакеты по 4–8 байт.

Хитрость с алгоритмом Рюкзака, который мы обсуждали, заключается в том, что он необычайно чувствителен (по сравнению с другими алгоритмами) к величине определенного параметра, W. Добавьте один бит к W, и вы удвоите время работы алгоритма. Мы не видели такого драматического отклика на изменения стоимости в других алгоритмах до этого, поэтому может показаться, что мы относимся к ранцу иначе - но это подлинный анализ того, как он реагирует неполиномиальным образом к изменениям в размере ввода.

Answer 3

Время выполнения алгоритма ранца связано не только с размером входа (n - количество предметов), но и с величиной входа (W - емкость рюкзака) O (nW), которая является экспоненциальной в как он представлен в компьютере в двоичном виде (2 ^ n). Сложность вычислений (то есть, как обработка выполняется внутри компьютера через биты) касается только размера входных данных , , а не их магнитуд / значения .

Не обращайте внимания на список значений / веса на мгновение. Допустим, у нас есть экземпляр с вместимостью ранца 2. W будет принимать два бита во входных данных. Теперь мы увеличим вместимость рюкзака до 4, оставив оставшуюся часть ввода. Наш вклад вырос только на один бит, но вычислительная сложность увеличилась в два раза. Если мы увеличим емкость до 1024, у нас будет только 10 бит ввода для W вместо 2, но сложность увеличилась в 512 раз. Сложность по времени растет экспоненциально в размере W в двоичном (или десятичном) представлении .

Другим простым примером, который помог мне понять псевдополиномиальную концепцию, является алгоритм наивного тестирования на простоту. Для заданного числа n мы проверяем, делится ли оно равномерно на каждое целое число в диапазоне 2..√n, поэтому алгоритм выполняет √ (n − 1) шагов. Но здесь n - это величина ввода, а не его размер.

                     Now The regular O(n) case

В отличие от этого, поиск в массиве для данного элемента выполняется за полиномиальное время: O (n). Требуется не более n шагов, а здесь n - размер ввода (длина массива).

[см. Здесь]

Расчетные биты, необходимые для хранения десятичного числа

Answer 4

Насколько я понимаю, мощность была бы O (Вт), если бы входная мощность была массивом [1,2, ..., Вт] , который имеет размерW. Но ввод емкости - это не массив чисел, а целое число.Сложность по времени составляет примерно отношение к размеру ввода. размер целого числа - это НЕ значение целого числа, а количество битов, представляющих его.Позже мы конвертируем это целое число W в массив [1,2, ..., W] в алгоритме, что приводит людей к ошибочному мнению, что W - это размер, но этот массив не является входным, а само целое число.

Думайте о вводе как о «массиве материала», а о размере - как «сколько материала в массиве».Входные данные элемента - это массив из n элементов в массиве, поэтому size = n. Ввод емкости - это НЕ массив чисел W в нем, , а одно целое число , представленное массивом битов журнала (W).Увеличьте его размер на 1 (добавив 1 значащий бит), W удваивается, поэтому время выполнения увеличивается вдвое, отсюда и экспоненциальная сложность времени.