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