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