WikiDer > Псевдополиномиальное время

Pseudo-polynomial time

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

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

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

Примеры

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

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

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

В случае простоты оказывается, что существует другой алгоритм для проверка того, есть ли п премьер (обнаружен в 2002 году), который работает во времени .

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

в проблема с рюкзаком, нам дано предметы с весом и ценность вместе с максимальной грузоподъемностью рюкзака .Цель - решить следующую задачу оптимизации; неформально, как лучше всего поместить предметы в рюкзак, чтобы получить максимальную выгоду?

максимизировать
при условии и .

Решение этой проблемы NP-жесткий, поэтому алгоритм с полиномиальным временем невозможен, если P = NP. Однако временной алгоритм возможен с использованием динамическое программирование; поскольку число только нужно бит для описания, этот алгоритм выполняется за псевдополиномиальное время.

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

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

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

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

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