Что такое псевдополиномиальное время? Чем он отличается от полиномиального времени?

Ответ 1

Чтобы понять разницу между полиномиальным временем и псевдополиномиальным временем, нам нужно начать с формализации того, что означает "полиномиальное время".

Общей интуицией для полиномиального времени является "время O (n ^k) для некоторого k." Например, сортировка выбора выполняется во времени O (n ²), что является полиномиальным временем, тогда как решение грубой силы TSP требует времени O (n & middot; n!), которое не является полиномиальным временем.

Все эти временные ряды относятся к некоторой переменной n, которая отслеживает размер ввода. Например, при сортировке выбора n относится к числу элементов в массиве, тогда как в TSP n относится к числу узлов на графике. Чтобы стандартизировать определение того, что в действительности означает "n", формальное определение временной сложности определяет "размер" проблемы следующим образом:

Размер ввода для проблемы - это количество бит, необходимое для записи этого ввода.

Например, если вход в алгоритм сортировки представляет собой массив из 32-битных целых чисел, тогда размер ввода будет 32n, где n - количество записей в массиве. В графе с n узлами и m ребрами вход может быть указан как список всех узлов, за которыми следует список всех ребер, для которых требуются бит & Omega; (n + m).

Учитывая это определение, формальное определение полиномиального времени таково:

Алгоритм работает в полиномиальном времени, если его время выполнения равно O (x ^k) для некоторой константы k, где x обозначает количество бит ввода, заданного алгоритму.

При работе с алгоритмами, которые обрабатывают графики, списки, деревья и т.д., это определение более или менее согласуется с обычным определением. Например, предположим, что у вас есть алгоритм сортировки, который сортирует массивы из 32-битных целых чисел. Если вы используете что-то вроде сортировки сортировки для этого, время выполнения, как функция количества входных элементов в массиве, будет O (n ²). Но как n, количество элементов во входном массиве, соответствует количеству бит ввода? Как упоминалось ранее, количество бит ввода будет x = 32n. Поэтому, если мы выражаем время выполнения алгоритма в терминах x, а не n, мы получаем, что среда выполнения O (x ²), и поэтому алгоритм работает в полиномиальное время.

Аналогично предположим, что вы выполняете поиск по глубине > на графике, который занимает время O (m + n), где m - количество ребер в graph и n - количество узлов. Как это связано с количеством бит ввода? Ну, если мы предположим, что вход задан как список смежности (список всех узлов и ребер), то, как упоминалось ранее, количество входных бит будет равно x = & Omega; (m + n). Следовательно, время выполнения будет O (x), поэтому алгоритм работает в течение полиномиального времени.

function isPrime(n):
    for i from 2 to n - 1:
        if (n mod i) = 0, return false
    return true

Итак, какова временная сложность этого кода? Ну, этот внутренний цикл запускает O (n) раз и каждый раз выполняет некоторую работу по вычислению n mod я (как действительно консервативная верхняя граница, это, безусловно, может быть сделано за время O (n ³)). Поэтому этот общий алгоритм работает во времени O (n ⁴) и, возможно, намного быстрее.

В 2004 году три компьютерных ученых опубликовали документ под названием PRIMES в P, который дает алгоритм полиномиального времени для проверки того, является ли число простым. Это считалось важным результатом. Так что же такое? Разве у нас уже нет алгоритма с полиномиальным временем, а именно: выше?

К сожалению, мы этого не делаем. Помните, что формальное определение временной сложности говорит о сложности алгоритма как функции количества бит ввода. Наш алгоритм работает во времени O (n ⁴), но что это такое, как функция количества входных бит? Ну, выписывая число n принимает O (log n) бит. Поэтому, если мы хотим, чтобы x было числом бит, необходимым для записи ввода n, время выполнения этого алгоритма на самом деле O (2 ^4x), которое не является многочленом от x.

Это основа различия между полиномиальным временем и псевдополиномиальным временем. С одной стороны, наш алгоритм O (n ⁴), который выглядит как многочлен, но, с другой стороны, при формальном определении полиномиального времени это не полиномиальное время.

Чтобы получить интуицию, почему алгоритм не является алгоритмом с полиномиальным временем, подумайте о следующем. Предположим, я хочу, чтобы алгоритм выполнял большую работу. Если я выпишу такой ввод:

10001010101011

то для завершения потребуется немного наихудшего времени, например T. Если теперь добавить один бит в конец номера, например:

100010101010111

Теперь время выполнения (в худшем случае) будет 2T. Я могу удвоить объем работы алгоритма, просто добавив еще один бит!

Алгоритм работает в псевдополиномном времени, если время выполнения - это некоторый полином в числовом значении ввода, а не в количестве бит, необходимых для его представления. Наш первичный алгоритм тестирования представляет собой алгоритм псевдополиномиального времени, поскольку он работает во времени O (n ⁴), но это не алгоритм полиномиального времени, поскольку в зависимости от количества бит x, требуемого для выписывания вход, время выполнения O (2 ^4x). Причина, по которой бумага "PRIMES in P" была настолько значительна, заключалась в том, что ее время выполнения было (примерно) O (log ¹² n), которое в зависимости от количества бит равно O (x ¹²).

Так почему это имеет значение? Ну, у нас много псевдополиномиальных алгоритмов времени для факторинговых целых чисел. Однако эти алгоритмы являются, технически говоря, алгоритмами экспоненциального времени. Это очень полезно для криптографии: если вы хотите использовать шифрование RSA, вы должны быть уверены, что мы не сможем легко вычислять числа. Увеличивая количество бит в числах до огромного значения (скажем, 1024 бит), вы можете сделать количество времени, которое должен выполнить алгоритм псевдополиномиального факторинга, настолько велико, что было бы совершенно и совершенно невозможно измерить номера. Если, с другой стороны, мы можем найти алгоритм факторинга многочленов, это не обязательно так. Добавление большего количества бит может заставить работу расти на много, но рост будет только полиномиальным ростом, а не экспоненциальным ростом.

Тем не менее, во многих случаях алгоритмы псевдополиномиального времени отлично подходят, потому что размер чисел не будет слишком большим. Например, подсчет сортировки имеет время выполнения O (n + U), где U - наибольшее число в массиве. Это псевдополиномиальное время (потому что числовое значение U требует битов O (log U) для записи, поэтому время выполнения экспоненциально зависит от размера ввода). Если мы искусственно ограничиваем U так, что U не слишком велик (скажем, если мы будем обозначать U равным 2), то время выполнения равно O (n), что на самом деле является полиномиальным временем. Вот как работает radix sort: обрабатывая числа по одному бит за раз, время выполнения каждого раунда равно O (n), поэтому общая продолжительность выполнения O (n log U). На самом деле это полиномиальное время, потому что выписывание n чисел для сортировки использует & Omega; (n) бит, а значение log U прямо пропорционально количеству бит, необходимых для записи максимального значения в массиве.

Надеюсь, это поможет!

Ответ 2

Псевдополиномиальная временная сложность означает многочлен от значения/величины ввода, но экспоненциальный по размеру ввода.

По размеру мы подразумеваем количество бит, необходимых для записи ввода.

Из псевдокода ранца мы можем найти временную сложность O (nW).

// Input:
// Values (stored in array v) 
// Weights (stored in array w)
// Number of distinct items (n) //
Knapsack capacity (W) 
for w from 0 to W 
    do   m[0, w] := 0 
end for  
for i from 1 to n do  
        for j from 0 to W do
               if j >= w[i] then 
                      m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) 
              else 
                      m[i, j] := m[i-1, j]
              end if
       end for 
end for

Здесь W не является многочленом по длине ввода, что делает его псевдополиномиальным.

Пусть s - количество бит, необходимое для представления W

i.e. size of input= s =log(W) (log= log base 2)
-> 2^(s)=2^(log(W))
-> 2^(s)=W  (because  2^(log(x)) = x)

Теперь running time of knapsack= O (nW) = O (n * 2 ^ s) который не является многочленом.