Слабая NP-полнота - Weak NP-completeness

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

Например, NP-жесткий проблема с рюкзаком может быть решена динамическое программирование алгоритм, требующий полинома количества шагов по размеру рюкзака и количеству предметов (при условии, что все данные масштабируются до целых чисел); однако время выполнения этого алгоритма экспоненциальное время поскольку входные размеры предметов и рюкзака логарифмические по величине. Однако, как отметили Гэри и Джонсон (1979), «А псевдополиномиальное время алгоритм… будет отображать «экспоненциальное поведение» только при столкновении с экземплярами, содержащими «экспоненциально большие» числа, [что] может быть редкостью для интересующего нас приложения. Если так, этот тип алгоритма может служить нашим целям почти так же хорошо, как и алгоритм с полиномиальным временем ». Другой пример для слабо NP-полной задачи - это проблема суммы подмножества.

Связанный термин сильно NP-полный (или унарный NP-полный) относится к тем проблемам, которые остаются NP-завершенными, даже если данные закодированы в унарный (то есть, если данные «малы» по сравнению с общим размером ввода).

Рекомендации

• М. Р. Гарей и Д. С. Джонсон. Компьютеры и несговорчивость: руководство по теории NP-полноты. W.H. Фриман, Нью-Йорк, 1979.
• Л. Холл. Вычислительная сложность. Университет Джона Хопкинса.