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

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

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

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

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

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

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

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

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

Определение

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

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

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

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

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

Тонкости

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

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

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

Ссылки

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

[:0-1] Перейти обратно: Перейти обратно: ^а ^б ^с Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

[2] Шрийвер, Александр (2003). «Предварительные сведения об алгоритмах и сложности». Комбинаторная оптимизация: многогранники и эффективность . Том. 1. Спрингер. ISBN 3-540-44389-4 .

[1]

[2]