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

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

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

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

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

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

В случае простоты числа оказывается, что существует другой алгоритм проверки того, является ли n простым числом (открытый в 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(нВт)}$${\displaystyle W}$${\displaystyle \log Вт}$

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

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

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

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

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

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