ProghubPH

Чем отличается NP-трудная задача от NP-полной?

 один вариант
Задача NP-полна, если к ней сводится любая задача из NP. Задача NP-трудна, если она лежит в NP и NP-трудна.
Задача NP-трудна, если к ней сводится любая задача из NP. Задача NP-полна, если она лежит в NP и NP-трудна.
Задача NP-трудна, если существует подсказка, размер которой с точностью до полинома не превышает размер входа, и существует полиномиальный алгоритм решающий задачу по данной подсказке. Задача NP-полна, если она лежит в NP и NP-трудна.