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