Определения алгоритма, работающего за полиномиальное время и сильно полиномиальное время

Википедия определяет это как

Считается, что алгоритм имеет полиномиальное время, если его время выполнения ограничено сверху полиномиальным выражением в размере входных данных для алгоритма, т. Е. для некоторой константы k. $T(n) = O(n^k)$

Алгоритм работает за сильно полиномиальное время, если [8]

количество операций в арифметической модели вычислений ограничено полиномом от числа целых чисел во входном экземпляре; и

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

В Бернхард Корте, Jens Vygen, комбинаторной оптимизации :

Определение 1.4.

Говорят, что алгоритм с рациональным вводом работает за полиномиальное время, если

существует целое число k такое, что оно выполняется за время , где n - размер ввода, и $O(n^k)$

все числа в промежуточных вычислениях могут быть сохранены с битами. $O(n^k)$

Говорят, что алгоритм с произвольным вводом работает за строго полиномиальное время, если

существует целое число k такое, что оно выполняется за время для любого ввода, состоящего из n чисел и $O(n^k)$

он работает за полиномиальное время для рационального ввода.

Пожалуйста, поправьте меня, если я ошибаюсь. Ниже приведены буквальные различия, которые я заметил:

Для алгоритмов полиномиального времени определение Корта и Выгена - это «определение Википедии + пространство хранения полинома».
Для сильно полиномиальных алгоритмов времени определение Корта и Вигена и определение Википедии требуют полиномиального времени в объеме входной памяти. Но для K и V дополнительно требуется полиномиальное время в количестве чисел в любом входе, в то время как в Википедии дополнительно требуется полиномиальное пространство для хранения во входном размере.

Значит, определения K и V и Wikipedia для этих двух понятий эквивалентны соответственно? Какие еще различия и отношения между ними?

Спасибо и всего наилучшего!

complexity-theory StackExchange для всех
источник

раздел википедии сразу после defn имеет довольно хорошее объяснение, не так ли ясно? это связано с тем, сколько битов представляют числа, и очень большие числа могут влиять на измерения сложности "вверх". думаю, что определения с K & V, вероятно, "почти" эквивалентны. Что касается рациональных входных данных, необходимо доказательство того, что арифметика рациональных чисел не увеличивает их размер в значительной степени. думаю, это можно показать, найдя на ЖК-дисплее все входы и выполнив всю арифметику в цифрах относительно ЖК-дисплея.

vzn

@vzn: объяснение в Википедии (1) прилично для арифметики против машины Тьюринга, но довольно поверхностно в отношении цели и определения с поли-полицией, а (2) было совершенно неверно в том, что иллюстрирует GCD.

Алексей

Ответы:

Прежде чем приступить к формальным определениям, рассмотрим, что стремится отличить «сильно / слабо» классификация.

Во-первых, рассмотрите возможность запуска любого из них на машине Тьюринга. Оба будут выполняться за несколько шагов полинома по длине двоично-кодированного ввода. Следовательно, число арифметических операций, выполняемых обоими, должно быть полиномиальным по длине двоично-кодированного ввода . Следовательно, для обеих машин Тьюринга время работы будет расти полиномиально с ростом числа входных значений или их величин. Чтобы подчеркнуть последнее, обратите внимание, что даже сильный будет делать больше шагов ТМ на больших величинах (ему нужно как минимум прочитать дополнительные биты). Ни при каких обстоятельствах человек не становится экспоненциальным (как в случае с несвязанным псевдополиномиальным временем). С одной только машиной Тьюринга фундаментальное различие не кажется заметным.

$O(1)$

Набор алгоритмов, которые выполняются по числу арифметических операций, полиномиальных по числу входных чисел, хорошо определен, но перекрывается с классом алгоритмов, которые принимают экспоненциальное число шагов TM по длине двоично-кодированного ввода (см. Примеры ). Следовательно, для этого набора свойства во втором абзаце не будут сохраняться. Чтобы исключить нежелательное пересечение, мы добавляем условие для полиномиального пространства TM [*].

В [1] это указано двумя способами:

Алгоритм выполняется за строго полиномиальное время, если алгоритм является алгоритмом полиномиального пространства, и выполняет ряд элементарных арифметических операций, ограниченных полиномом по числу входных чисел.
Полиномиальный алгоритм - это алгоритм полиномиального пространства (в нашей стандартной модели машины Тьюринга) и алгоритм полиномиального времени в арифметической модели (см. Этот вопрос для пояснения).

$O(n^3)$ $O(n^2)$

[*] Второе условие везде задается как полиномиальное пространство, тогда как требование полиномиального времени имеет для меня больше смысла. Первый более содержательный, но странный. Существуют ли сильно-полиномиальные алгоритмы, которые занимают больше полиномиального времени? Обратите внимание, что пример повторного возведения в квадрат не занимает ни полиномиального времени, ни полиномиального пространства.

[1] Grötschel, Martin; Ласло Ловаш, Александр Шрайвер (1988). «Сложность, оракулы и численные вычисления». Геометрические алгоритмы и комбинаторная оптимизация. Springer. ISBN 0-387-13624-X.

алексей
источник