И я обещал рассказать про то, что такое NP-задачи.

Определение NP-задачи такое: задача Q относится к классу NP, если
1) Она требует ответа вида Q(x)="да/нет" в зависимости от параметра x
и
2) Ответ "да" может быть доказан некоторой "справкой", проверяемой за полиномиальное время. Формально — существует такой алгоритм Check(x,S), "проверяющий" за полиномиальное по длине входа x время полиномиальный по длине входа x сертификат S:
- для любого x, для которого Q(x)="да", существует S, такой, что Check(x,S)="да";
- ни для одного x, для которого Q(x)="нет", не существует такого S, чтобы Check(x,S)="да"
(плюс ограничения на длину S и на время работы Check).

Стоит отметить, что постановка тут несимметрична по "да/нет": если вопрос Q="x верблюд?" принадлежит классу NP, ибо взятая в зоопарке справка S проверяется процедурой
Check(x,S)="проверить бланк справки, печать зоопарка и совпадение указанного там животного с x"
(при том, что предъявление S="мятая салфетка" не означает, что x не верблюд — а только то, что данная S этого не доказывает),
то где брать справку, что ты не верблюд, совершенно непонятно.

Менее абстрактный пример — вопрос о том, является ли данное натуральное число N составным, принадлежит классу NP. "Справкой" будет его разложение на два сомножителя, S=(a,b); процедура проверки —
Check(N,S)=
- проверить, что S=(a,b), где a,b натуральные и больше 1 (а то норовят всякие подсунуть строку вместо числа на вход).
- проверить, что N=ab.
(Последнее даже при выполнении умножения "в столбик" требует ~n^2 операций, где n — число цифр в записи N)

А вот принадлежность вопроса "является ли N простым" классу NP совершенно неочевидна. Потому что проверка "в лоб" подразумевала бы перебор делителей от 1 до корня из N — и это даже для N порядка 10^100 ну совершенно нереалистично. А как бы могла быть устроена короткая и быстро проверяемая "справка о простоте" — на вид непонятно.
(На самом деле, этот вопрос даже классу P принадлежит — но без дополнительных предположений это результат начала 2000-х: см. Agrawal, Kayal, Saxena, PRIMES in P, Annals of Mathematics, 2004 + https://en.wikipedia.org/wiki/AKS_primality_test )