Сильно-полиномиальное время

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

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

Вычислительные модели

Две распространенные вычислительные модели — это модель машины Тьюринга и арифметическая модель : ^{[1] : 32}

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

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

• Алгоритм Евклида выполняется за полиномиальное время в модели Тьюринга, но не в арифметической модели.
• Алгоритм, который считывает n чисел, а затем вычисляет их путем повторного возведения в квадрат , работает за полиномиальное время в арифметической модели, но не в модели Тьюринга. Это происходит потому, что количество бит, требуемых для представления результата, экспоненциально зависит от размера входных данных. ${\displaystyle 2^{2^{n}}}$

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

Определение

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

1. количество операций в арифметической модели вычислений ограничено полиномом от количества целых чисел во входном экземпляре; и
2. Пространство, используемое алгоритмом, ограничено полиномом от размера входных данных.

Любой алгоритм с этими двумя свойствами может быть преобразован в алгоритм полиномиального времени путем замены арифметических операций подходящими алгоритмами для выполнения арифметических операций на машине Тьюринга . Второе условие является строго необходимым: учитывая целое число (которое занимает место, пропорциональное n в модели машины Тьюринга), можно вычислить с помощью n умножений, используя повторное возведение в квадрат . Однако пространство, используемое для представления , пропорционально , ​​и, таким образом, экспоненциально, а не полиномиально в пространстве, используемом для представления входных данных. Следовательно, невозможно выполнить это вычисление за полиномиальное время на машине Тьюринга, но его можно вычислить с помощью полиномиального числа арифметических операций. ${\displaystyle 2^{n}}$ ${\displaystyle 2^{2^{n}}}$ ${\displaystyle 2^{2^{n}}}$ ${\displaystyle 2^{n}}$

Однако для первого условия существуют алгоритмы, которые работают за число шагов машины Тьюринга, ограниченное полиномом по длине двоично-кодированного ввода, но не выполняют число арифметических операций, ограниченное полиномом по количеству входных чисел. Одним из примеров является алгоритм Евклида для вычисления наибольшего общего делителя двух целых чисел. При наличии двух целых чисел и алгоритм выполняет арифметические операции над числами с не более чем битами. В то же время число арифметических операций не может быть ограничено числом целых чисел во входных данных (которое в этом случае является постоянным, во входных данных всегда есть только два целых числа). Из-за последнего наблюдения алгоритм не работает за строго полиномиальное время. Его реальное время работы зависит от длин и в битах , а не только от числа целых чисел во входных данных. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle O(\log a+\log b)}$ ${\displaystyle O(\log a+\log b)}$ ${\displaystyle a}$ ${\displaystyle b}$

Алгоритм, который выполняется за полиномиальное время, но не является сильно полиномиальным, называется работающим за слабо полиномиальное время . ^[2] Хорошо известным примером задачи, для которой известен слабо полиномиальный алгоритм, но неизвестно, допускает ли он сильно полиномиальный алгоритм, является линейное программирование . Слабо полиномиальное время не следует путать с псевдополиномиальным временем , которое зависит от величин значений в задаче, а не от длин, и не является истинно полиномиальным временем.

Тонкости

Чтобы задать арифметическую модель, существует несколько способов определения операции деления. Результат деления целого числа a на другое целое число b может быть одним из: ^{[1] : 33}

1. Рациональное число a/b (т.е. не сокращенное, поскольку сокращение не может быть выполнено за сильно полиномиальное время).
2. Рациональное число a/b, за исключением случая, когда заранее известно, что a/b — целое число; в этом случае это целое число a/b.
3. Рациональное число a/b, за исключением случая, когда a/b — целое число, в этом случае оно равно целому числу a/b.
4. Целое число floor(a/b).

Во всех версиях строго полиномиальное время подразумевает полиномиальное время в модели Тьюринга.

Ссылки

1. Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация, Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер документа : 10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, г-н  1261419
2. Schrijver, Alexander (2003). "Предварительные сведения об алгоритмах и сложности". Комбинаторная оптимизация: многогранники и эффективность . Том 1. Springer. ISBN 3-540-44389-4.