Cтраница 2
Для задачи о взвешенном паросочетании известны полиномиальные алгоритмы ( см., например, [ 11, гл. [16]
Эти таблицы демонстрируют причину, по которой полиномиальные алгоритмы обычно считаются более предпочтительными по сравнению с экспоненциальными. Эта точка зрения, различающая, с одной стороны, полиномиальные алгоритмы, а с другой стороны, экспоненциальные, является отправной точкой в определении труднорешаемых задач и NP-полных задач. [17]
Последнее означает, что если будет найден полиномиальный алгоритм для точного решения хотя бы одной NP-полной задачи, то за полиномиальное время можно будет решить любую задачу этого класса. [18]
Для доказательства этого утверждения предположим, что существует полиномиальный алгоритм решения нашей задачи упорядочения, заданной в виде задачи распознавания. [19]
Первый результат говорит о том, что для получения полиномиального алгоритма нельзя допускать произвольные значения времен выполнения. Если эти времена не произвольные, то их значения должны выбираться из некоторого набора допустимых величин. Второй результат приводит к необходимости рассмотрения систем с одинаковыми временами выполнения заданий, по крайней мере в случае произвольного частичного упорядочения. [20]
Осуществляется с использованием многомерной пошаговой регрессии и линейного варианта полиномиального алгоритма МГУА. [21]
Для этого класса уравнений оно допускает решение с помощью полиномиального алгоритм ( относительно суммарной длины коэффициентов), о чем пойдет речь в следующем параграфе. [22]
Очевидно, любой псевдополиномиальный алгоритм решения задачи В является полиномиальным алгоритмом решения задачи Вр. Отсюда следует, что при условии & Ф JftP задача В не может иметь не только полиномиального, но и лсевдололшюмпального алгоритма решения, если задача Вр является ЖР-трудной. [23]
Очевидно, что такой граф строит-ся по 3 - КНФ полиномиальным алгоритмом. [24]
Принято считать задачу хорошо решаемой, если для ее решения существует полиномиальный алгоритм. [25]
Имеется, однако, несколько хороших доводов, оправдывающих выделение класса полиномиальных алгоритмов. Во-первых, хотя размеры задач растут, однако, время выполнения полиномиального алгоритма растет гораздо медленнее, чем экспоненциального, поэтому повышение качества программного обеспечения и усовершенствование компьютерной технологии могут уравновешивать увеличение размеров входов в полиномиальном случае гораздо дольше, чем в случае алгоритмов, выполняемых за экспоненциальное время. Для алгоритмов с экспоненциальным временем выполнения внезапный скачок, экспоненциальный взрыв, делает их неосуществимыми даже при небольшом увеличении размеров задачи. Есть и синтаксическое различие между полиномиальными и неполиномиальными алгоритмами: грубо говоря, полиномиальный алгоритм может быть запрограммирован с использованием данного числа циклов и без переходов, в то времл как более медленный алгоритм так запрограммировать нельзя. [26]
Алгоритм упорядочения, сложность которого ограничена полиномом от п, называется полиномиальным алгоритмом или алгоритмом, работающим полиномиальное время. Соответствующая задача называется полиномиально разрешимой. В дальнейшем мы будем называть алгоритм эффективным, если он полиномиален. В этой связи необходимо отметить, что задачи упорядочения, которые мы рассматриваем, относятся или могут быть сведены к конечным задачам в том схмысле, что множество их решений конечно. [27]
Далее при условии успешной работы экспоненциальных алгоритмов попытки найти для соответствующих задач полиномиальные алгоритмы не прекращаются. В действительности сам факт успешного применения экспоненциальных алгоритмов дает основания для предположения, что они каким-то образом выявляют некоторые существенные особенности решаемых задач и что более глубокое их исследование может привести к дальнейшему улучшению методов. [28]
Заметим, что это доказательство теоремы Дилуорса предоставляет в наше распоряжение и некий полиномиальный алгоритм, позволяющий строить наименьшее цепное разбиение частично упорядоченного множества, а также наибольшую антицепь в нем. [29]
VP-полноты задачи о выполнимости необходимо показать, что наличие для нее детерминированного полиномиального алгоритма влечет за собой наличие детерминированного полиномиального алгоритма для любой задачи 5, входящей в NP. Это означает, что 5 полиномиально сводится к задаче о выполнимости. [30]