Давайте я закончу рассказ про NP и вокруг того. Мы пока сказали, что такое класс NP.
В начале 1970-х поняли две вещи: во-первых, в классе NP есть "самая сложная задача" — к которой любая другая NP-задача за полиномиальное время сводится. И во-вторых, что таких задач (сводящихся друг к другу) много.

Предъявить одну такую задачу совсем просто: собственно говоря, она практически уже выписана выше. А именно: пусть нам задан алгоритм C и полиномы P_1, P_2.
Q(x)="найдётся ли второй вход S, длины |S|<P_1(|x|), на котором за время не больше P_2(|x|) алгоритм C закончит работу и выдаст "да"? "

Такая задача явно принадлежит классу NP: если S уже задан, то нужно просто "в режиме интерпретатора" сделать P_2(|x|) шагов заданного алгоритма C и проверить, куда мы придём.
И любая NP-задача к ней сводится — для неё C это тот самый её алгоритм Check из определения!
Так что — вот наш первый пример NP-полной задачи.

Из него сразу можно получить ещё один — выполнимость булевской формулы. Допустим, что у нас написана булевская формула из переменных, их отрицаний (¬), конъюнкций (И, ⋀) и дизъюнкций (ИЛИ, ⋁). Можно ли подставить вместо переменных булевские единицы и нули (True и False) так, чтобы вся формула давала единицу?
Очевидно, что эта задача принадлежит классу NP: сертификат это как раз то, что нужно подставить. А почему она NP-полна?

Достаточно к ней свести уже увиденную нами NP-полную задачу, "найдётся ли S длины |S|<P_1(|x|) такой, что C(x,S)="да" за время P_2(|x|)".
Посмотрим на "протокол работы алгоритма C": закодируем нулями и единицами состояние каждой ячейки памяти в каждый момент времени. Тогда то, что набор нулей и единиц корректно кодирует протокол — это большая булевская формула, что в каждый момент времени и в каждой ячейке переход от этого момента времени к следующему выполнен правильно. Начальные условия (где нужно написать, что часть начальных данных это вход x, поставить пишуще-читающую головку машины Тьюринга на исходную позицию и в начальном состоянии, и так далее) и то, что алгоритм заканчивает работу и печатает "да" — это тоже просто требование на часть переменных (подстановка нулей и единиц вместо некоторых из них). И вот и всё сведение!

Более того — такая формула это всегда большая-большая конъюнкция довольно простых выражений "для любого t для любого места m [переход в точке пространства-времени (m,t) выполнен правильно]". Так что даже вопрос про такие формулы уже NP-полон.

Если мысленно собрать все переходы из логических элементов — а именно, достаточно иметь лишь И-НЕ — то у нас будет формула вида "переменная, приписанная к выходу каждого логического элемента, принимает то значение, которое задают его входы".

А это несложно задать конъюнкцией четырёх дизъюнкций: утверждение
"c=f(a,b)"
равносильно тому, что для каждой пары возможных значений a_0, b_0 мы пишем
"(a не равно a_0) ИЛИ (b не равно b_0) ИЛИ (с равно f(a_0,b_0))",
где вместо "переменная равна константе" мы ставим саму переменную, если константа это 1 и её отрицание, если константа это 0. Собственно, И-НЕ таким образом задаётся как "c=И-НЕ (a,b)" <=>
(¬a ИЛИ ¬b ИЛИ ¬c) И
(¬a ИЛИ b ИЛИ c) И
(a ИЛИ ¬b ИЛИ c) И
(a ИЛИ b ИЛИ c);
строчки тут соответствуют наборам входов и значениям 11->0, 10->1, 01->1, 00->1.

Так что NP-полна задача выполнимости булевской формулы, которая есть большая-большая конъюнкция скобок, в каждой из которых дизъюнкция всего-то трёх переменных или их отрицаний. И эта задача называется 3-SAT.