Слабая NP-полнота
По вычислительной сложности NP -полная (или NP-трудная ) задача является слабо NP-полной (или слабо NP-трудной), если существует алгоритм решения задачи, время выполнения которого полиномиально от размерности задачи и величин задействованные данные (при условии, что они заданы в виде целых чисел по основанию двойки ), а не логарифмы их величин . Такие алгоритмы технически являются экспоненциальными функциями размера входных данных и поэтому не считаются полиномиальными . [1]
Например, задача NP-жесткого рюкзака может быть решена с помощью алгоритма динамического программирования, требующего количества шагов, полиномиального по размеру рюкзака и количеству предметов (при условии, что все данные масштабируются до целых чисел); однако время выполнения этого алгоритма является экспоненциальным , поскольку входные размеры объектов и рюкзака являются логарифмическими по своим величинам. Однако, как заметили Гари и Джонсон (1979), « алгоритм с псевдополиномиальным временем … будет демонстрировать «экспоненциальное поведение» только тогда, когда сталкивается с экземплярами, содержащими «экспоненциально большие» числа, [что] может быть редкостью для интересующего нас приложения. Если это так, то этот тип алгоритма может служить нашим целям почти так же хорошо, как и алгоритм с полиномиальным временем». Другим примером слабо NP-полной задачи является задача о сумме подмножеств .
Соответствующий термин « сильно NP-полный » (или унарный NP-полный) относится к тем проблемам, которые остаются NP-полными, даже если данные закодированы в унарном формате , то есть если данные «маленькие» по отношению к общему входному размеру. [2]
Сильная и слабая NP-трудность в сравнении с сильными и слабыми алгоритмами с полиномиальным временем
[ редактировать ]Предполагая P ≠ NP, для вычислительных задач с целыми числами справедливы следующие условия: [3]
- Если задача является слабо NP-трудной , то она не имеет алгоритма со слабо полиномиальным временем (полиномиальным по числу целых чисел и количеству бит в наибольшем целом), но может иметь алгоритм псевдополиномиального времени (полиномиальный по числу целых чисел и величину наибольшего целого числа). Примером является проблема с разделами . И слабая NP-трудность, и слабое полиномиальное время соответствуют кодированию входных агентов в двоичном кодировании .
- Если задача сильно NP-трудна , то для нее даже не существует алгоритма с псевдополиномиальным временем . Он также не имеет полностью полиномиальной схемы аппроксимации по времени . Примером может служить проблема с тремя разделами . И сильная NP-жесткость, и псевдополиномиальное время соответствуют кодированию входных агентов в унарном кодировании .
Ссылки
[ редактировать ]- ^ Г-н Гэри и Д.С. Джонсон. Компьютеры и трудноразрешимость: Руководство по теории NP-полноты . У. Х. Фриман, Нью-Йорк, 1979 г.
- ^ Л. Холл. Вычислительная сложность . Университет Джонса Хопкинса.
- ^ Демейн, Эрик. «Алгоритмические нижние границы: развлечения с доказательствами твердости, лекция 2» .