Псевдополиномиальное время - Pseudo-polynomial time

В теория сложности вычислений, числовой алгоритм работает в псевдополиномиальное время если это Продолжительность это многочлен в числовое значение входных данных (наибольшее целое число, представленное во входных данных), но не обязательно в длина входных данных (количество битов, необходимых для его представления), что имеет место для полиномиальное время алгоритмы.

В общем, числовое значение ввода экспоненциально зависит от длины ввода, поэтому алгоритм псевдополиномиального времени не обязательно работает за полиномиальное время по отношению к длине ввода.

An НП-полный проблема с известными алгоритмами псевдополиномиального времени называется слабо NP-полный.An НП-полный проблема называется сильно NP-полный если доказано, что это не может быть решено с помощью алгоритма псевдополиномиального времени, если P = NP. Сильные / слабые виды NP-твердость определяются аналогично.

Примеры

Проверка на первичность

Рассмотрим проблему проверка того, является ли число п премьер, наивно проверив, нет ли числа в ${\displaystyle \{2,3,\dots ,{\sqrt {n}}\}}$ разделяет ${\displaystyle n}$ равномерно. Этот подход может занять до ${\displaystyle {\sqrt {n}}-1}$ подразделений, которая является сублинейной в значение n но экспоненциально в длина n (который о ${\displaystyle \log(n)}$). Например, число п немного меньше чем 10,000,000,000 потребуется примерно до 100 000 дивизий, даже если длина п всего 11 цифр. Более того, можно легко записать ввод (скажем, 300-значное число), для которого этот алгоритм нецелесообразен. Поскольку вычислительная сложность измеряет сложность по отношению к длина для (закодированного) входа этот наивный алгоритм на самом деле экспоненциальный. Это являетсяправда, время псевдополиномиальное.

Сравните этот алгоритм с настоящим полиномиальным числовым алгоритмом - скажем, простым алгоритмом сложения: добавление двух 9-значных чисел занимает около 9 простых шагов, и в целом алгоритм действительно линейен по длине входных данных. По сравнению с фактическими добавляемыми числами (в миллиардах) алгоритм можно было бы назвать «псевдологарифмическим временем», хотя такой термин не является стандартным. Таким образом, сложение 300-значных чисел не является непрактичным. Аналогично, деление в столбик квадратично: м-цифровое число можно разделить на п-цифровой номер в ${\displaystyle O(mn)}$ шаги (см. Обозначение Big O.)

В случае простоты оказывается, что существует другой алгоритм для проверка того, есть ли п премьер (обнаружен в 2002 году), который работает во времени ${\displaystyle O((\log {n})^{6})}$.

Задача о рюкзаке

в проблема с рюкзаком, нам дано ${\displaystyle n}$ предметы с весом ${\displaystyle w_{i}}$ и ценность ${\displaystyle v_{i}}$вместе с максимальной грузоподъемностью рюкзака ${\displaystyle W}$.Цель - решить следующую задачу оптимизации; неформально, как лучше всего поместить предметы в рюкзак, чтобы получить максимальную выгоду?

максимизировать ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

при условии ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$ и ${\displaystyle x_{i}\in \{0,1\}}$.

Решение этой проблемы NP-жесткий, поэтому алгоритм с полиномиальным временем невозможен, если P = NP. Однако ${\displaystyle O(nW)}$ временной алгоритм возможен с использованием динамическое программирование; поскольку число ${\displaystyle W}$ только нужно ${\displaystyle \log W}$ бит для описания, этот алгоритм выполняется за псевдополиномиальное время.

Обобщение на нечисловые проблемы

Хотя понятие псевдополиномиального времени используется почти исключительно для числовых задач, эту концепцию можно обобщить: функция м является псевдополиномиальным, еслим(п) не больше, чем полиномиальная функция из размер проблемы п и дополнительное свойство входа, k(п). (Предположительно, k выбирается как нечто относящееся к проблеме.) Это делает числовые полиномиальные задачи особым случаем, принимая k быть числовым значением ввода.

Различие между значением числа и его длиной заключается в кодировании: если числовые входные данные всегда кодируются в унарный, тогда псевдополином совпадет с многочлен.

Смотрите также

• Сильно NP-полный
• Квазиполиномиальное время

Рекомендации

• Майкл Р. Гарей и Дэвид С. Джонсон. Компьютеры и непреодолимость: руководство по теории NP-полноты. W.H. Фримен и компания, 1979.