Факториально-временные алгоритмы и П / НП

Question

Это довольно легко увидеть, п! растет медленнее, чем что-либо, почти до степени N (скажем, 100 ^ N), и поэтому, если проблема считается NP завершенной, а одна возникла при n! алгоритм, который приближает решение, можно было бы сделать танец Снупи.

У меня есть 2 вопроса об этой ситуации:

1. Будет ли п! алгоритм считается решением за полиномиальное время? Факториал, безусловно, не является термином, возведенным в степень.
2. Если найти n! Решение означает, что у нас есть прилично быстрый алгоритм и так как n! растет быстрее, чем 2 ^ N, значит ли это, что для некоторых NP-полных задач не требуются эвристические / аппроксимационные алгоритмы (кроме неясных случаев)?

Конечно, эти два вопроса основаны на истинности первого абзаца; если я ошибся, пожалуйста, дайте мне знать.

Answer 1

1. Нет.факториальное время не является полиномиальным временем.Полиномиальное время обычно означает уравнение вида O (N ^k ), где N = количество обрабатываемых элементов, а k = некоторая постоянная.Важная часть заключается в том, что показатель степени является константой - вы умножаете N на некоторое число, которое является фиксированным, не зависящим от самого N.Алгоритм факториальной сложности означает, что число умножений не фиксировано - число умножений само увеличивается с N.

2. У вас, похоже, такая же проблема здесь,N ² будет полиномиальной сложностью.2 ^N не будет.Ваш основной принцип также ошибочен - алгоритм факториальной сложности не означает «у нас достаточно быстрый алгоритм», по крайней мере, как общее правило.Во всяком случае, вывод скорее противоположный: факторный алгоритм может быть практичным в нескольких особых случаях (т. Е., Когда N чрезвычайно мал), но становится непрактичным очень быстро с ростом N.

Давайте попробуем представить это в перспективе.Двоичный поиск - это O (log N).Линейный поиск O (N).При сортировке «медленными» алгоритмами являются O (N ² ) и «продвинутыми» алгоритмами O (N lg N).Сложность факториала (очевидно, достаточно) O (N!).

Попробуем привести к этому некоторые цифры, учитывая (на данный момент) только 10 пунктов.Каждое из них будет примерно в сколько раз дольше обрабатываться для 10 элементов вместо 1 элемента:

O (log N): 2
O (N): 10
O (N logN): 23
O (N ² ): 100
O (N!): 3 628 800

На данный момент я немного обманул и использую натуральныйлогарифм вместо логарифма с основанием 2, но мы здесь пытаемся только приблизительные оценки (и разница в любом случае является довольно небольшим постоянным фактором).

Как видите, скорость роста для факториала-сложность алгоритма на намного быстрее, чем для любого другого.Если мы расширим его до 20 пунктов, разница станет еще более существенной:

O (log N): 3
O (n): 20
O (N log N): 60
O (N ² ): 400
O (N!): 2 432 902 008 176 640 000

Скорость роста для N!настолько быстры, что они практически гарантированно будут непрактичными, за исключением случаев, когда количество элементов включает , о которых известно, что довольно мало.Для ухмылки, давайте предположим, что основные операции для процессов, описанных выше, могут выполняться в одном цикле машины.Просто ради аргумента (и для простоты расчетов) давайте предположим, что процессор 10 ГГц.Итак, база в том, что на обработку одного элемента уходит 0,1 нс.В этом случае с 20 элементами:

O (log N) = .3 нс
O (N) = 2 нс
O (N log N) = 6 нс
O (N ² ) = 40 нс
O (N!) = 7,7 года.

Answer 2

Довольно легко увидеть, что факториал (приблизительно) экспоненциальный в поведении.

Это может быть (очень грубо) приблизительно: n ⁿ (точнее, sqrt (2 & pi; n) (n / e) ⁿ ).

Итак, если вы нашли какой-то конкретный M, в котором вы думаете, что M ⁿ - хорошее приближение, вы (вероятно) ошибаетесь. 269! больше 100 ⁿ и как n! будет умножен на числа больше 100, он будет продолжать расти быстрее.