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

В теории сложности вычислений числовой алгоритм работает за псевдополиномиальное время , если время его работы является полиномом от числового значения входных данных (наибольшего целого числа, присутствующего на входных данных), но не обязательно от длины входных данных (числа битов, необходимых для его представления), что справедливо для с полиномиальным временем . алгоритмов ^[1]

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

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

Примеры

Тестирование на примитивность

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

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

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

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

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

максимизировать

\sum _{i=1}^{n}v_{i}x_{i}

при условии

\sum _{i=1}^{n}w_{i}x_{i}\leq W

и

x_{i}\in \{0,1\}

.

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

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

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

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

Сильная и слабая NP-трудность в сравнении с сильными и слабыми алгоритмами с полиномиальным временем

Предполагая P ≠ NP, для вычислительных задач с целыми числами справедливы следующие условия: ^[2]

Если задача является слабо NP-трудной , то она не имеет алгоритма со слабо полиномиальным временем (полиномиальным по числу целых чисел и количеству бит в наибольшем целом), но может иметь алгоритм псевдополиномиального времени (полиномиальный по числу целых чисел и величину наибольшего целого числа). Примером является проблема с разделами . И слабая NP-трудность, и слабое полиномиальное время соответствуют кодированию входных агентов в двоичном кодировании .

Если задача сильно NP-трудна , то для нее даже не существует алгоритма с псевдополиномиальным временем . Он также не имеет полностью полиномиальной схемы аппроксимации по времени . Примером может служить проблема с тремя разделами . И сильная NP-жесткость, и псевдополиномиальное время соответствуют кодированию входных агентов в унарном кодировании .

См. также

Ссылки

^ Майкл Р. Гэри и Дэвид С. Джонсон . Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . WH Freeman and Company, 1979.
^ Демейн, Эрик. «Алгоритмические нижние границы: развлечения с доказательствами твердости, лекция 2» .

[1] Майкл Р. Гэри и Дэвид С. Джонсон . Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . WH Freeman and Company, 1979.

[2] Демейн, Эрик. «Алгоритмические нижние границы: развлечения с доказательствами твердости, лекция 2» .

[1]

[2]