Псевдополиномиальные алгоритмы - верно ли мое понимание?

Question

В элегантном ответе, данном Фрудхви, на этот вопрос Что такое псевдополиномиальное время? Чем оно отличается от полиномиального времени? Установлено, среди многих других важных моментов, что при реальном формальном определении Сложности Времени TC их примерного алгоритма экспоненциально по x.

Я понял все в ответе, кроме этого пункта здесь. В ответе его пример alg - O (n ^ 4). Затем он заявляет, что формальное определение TC основано на количестве битов, необходимых для представления n. Итак, я ожидал, что он скажет, что TC будет O (x), где x - это число битов. Вместо этого он сказал, что это O (2 ^ 4x).

У меня есть представление о том, почему я запутался, и что я думаю, на самом деле происходит. Не могли бы вы сказать мне, если я сейчас прав?

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

Однако, что я теперь предполагаю, что он имеет в виду, и что я считаю правильным, так это: даже в формальном определении сложности времени время, затраченное на его пример и алгоритмы в целом действительно на самом деле основано на размере входного n и равно O (n ^ 4) (в его примере). Однако размер n растет по экспоненте с увеличением x.

Оба выражения временной сложности оба точны, но поскольку формальное определение Сложности Времени требует, чтобы время O (n ^ 4) было выражено как функция от x, а n растет экспоненциально с x, то в терминах x формальный TC - O (2 ^ 4x).

Это правильно? Большое спасибо, действительно!

Answer 1

Если я правильно понимаю ваш вопрос, ваше замешательство может быть легко и быстро выяснено.

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

Лучший способ понять это - всегда представлять входные данные, записанные на ленте машины Тьюринга.
Если у нас есть алгоритм, который принимает число n в качестве входных данных и вычисляет n-ое треугольное число с помощью цикла (то есть он выдает 1 + 2 + 3 + ... + n ) заманчиво сказать, что алгоритм является линейным, так как он принимает n шагов.

Это верно в том смысле, что алгоритм является линейным в n , но это не говорит нам о TC алгоритма, поскольку TC определяется в терминах кодирования число n не n само по себе.

Обычно обозначают кодировку n с .
Например, возможные кодировки 4:

       _ _ _
<4> = |1|0|0|
       ¯ ¯ ¯  
       _ _
<4> = |1|1|
       ¯ ¯  
       _
<4> = |4|
       ¯  
       _ _ _ _
<4> = |x|x|x|x|
       ¯ ¯ ¯ ¯  
       _
<4> = |A| 
       ¯

Первые три примера - это просто позиционные системы (база 2, 3, 10).
Четвертый пример вырожденного кодирования (это унарный код). Последний пример представляет собой пользовательскую кодировку, где каждый n имеет определенный символ из алфавита кодирования.

Хотя концепция кодирования может показаться тривиальной, требуется время, чтобы выпить.
Вы можете проверить: цифра .

Если мы возьмем двоичную кодировку, число n будет иметь кодировку длиной около l = log ₂ ( N ). * * тысяча шестьдесят-один TC описанного выше алгоритма был n = 2 ^l .
Таким образом, его TC является экспоненциальным .

Что если мы выбрали десятичную кодировку?
ТС был бы 10 ¹ .
Поначалу кажется сложным, что алгоритм не может иметь определенного TC, но на самом деле TC зависит от вычислительной модели, включая кодирование.

Обычно мы предполагаем работать в модели, где арифметические операции занимают только один шаг.
Например, суммирование двух чисел на машине Тьюринга требует O (l), в то время как на старших моделях принято делать это O (1).
К сожалению, эти предположения не всегда изложены.

На самом деле нас это не особо беспокоит, хотя при асимптотической работе с нотацией big-O изменение базы кодирования изменяет только его длину на постоянную.
В общем, если кодировка A может быть превращена в другую кодировку B за полиномиальное время, мы не будем указывать, работаем ли мы с A или B потому что даже в цепочке преобразования кодирования с помощью алгоритма у нас все еще есть полиномиальный алгоритм (если исходный был таким).
Связано: Полиномиальное сокращение времени .

Теперь должно быть легко понять определение Псевдополиномиального времени , данное Википедией.

В теории вычислительной сложности числовой алгоритм выполняется за псевдополиномиальное время, если его время выполнения является полиномом в числовом значении входных данных.

Answer 2

Формула O (2 ^4x ) может быть получена из свойств логарифма следующим образом:

• O (number_of_bits) = O (log ₂ n), где n - номер ввода
• O (2 ^{number_of_bits} ) = O (n), по определению логарифма
• Повышение обеих сторон до 4-й степени дает O (2 ^{4 * number_of_bits} ) = O (n ⁴ )

Источник путаницы связан с маркировкой значения простого кандидата с помощью n, а затем с использованием O (n ⁴ ) в остальной части объяснения. Лучший способ обойти это - начать с n, являющегося количеством битов, необходимых для представления p, простого числа-кандидата. С n битами значение p ограничено 2 ⁿ . Если алгоритм равен O (p ⁴ ), вы получите результат O (2 ^{4 * n} ) путем простой перемаркировки.

Обратите внимание, что оценка OP, согласно которой вычисление n mod i равно O (n ³ ), действительно консервативна. Это должно быть O ((log ₂ n) ³ ), потому что сложность мода зависит от количества бит, необходимых для представления числа, а не от самого числа. Это не меняет достоверность остальной части ответа.