На відміну від NP-повних задач, NP

-складні задачі не обов'язково мають розв'язок,

який можна перевірити за поліноміальний час, але вони є такими ж складними, або

навіть складнішими, ніж задачі класу

Це задача, розв'язок якої завжди може бути

знайдений за поліноміальний час, але перевірка розв'язку потребує

експоненційного часу.

NP

-складна задача — це задача, яку можна розв'язати за поліноміальний час

за допомогою детермінованих алгоритмів

Ц

е задача, яку можна

розв'язати тільки за допомогою жадібних алгоритмів і яка не має жодних обмежень

на час виконання.