Классы P и NP

С 2000 года Математический институт Клэя предлагает 1 миллион долларов за ответ на вопрос: равны ли P и NP? Никто не получил. Но ставки выше: если P = NP, вся криптография рушится за часы. RSA, TLS, Bitcoin - всё. Разница между $O(n^2)$ и $O(2^n)$ для $n = 100$: 10 000 операций против $10^{30}$ - больше атомов в Земле. Bitcoin-майнинг - намеренно NP-задача. Это не баг. Это архитектура.

• **Криптография** - RSA и Diffie-Hellman основаны на предположении, что факторизация и дискретный логарифм не в P; если P = NP - всё рухнет
• **Bitcoin и proof-of-work** - майнинг намеренно построен на NP-задаче: найти хэш трудно, проверить - мгновенно
• **SAT-солверы** - верификация чипов Intel, синтез схем в FPGA, планировщики компиляторов - всё через решение NP-задач приближёнными методами
• **Логистика** - маршрутизация FedEx и UPS, bin packing на складах Amazon - NP-трудные задачи, решаемые эвристиками

Класс P

С 2000 года Математический институт Клэя предлагает 1 миллион долларов за ответ на вопрос: равны ли P и NP? Никто не получил. Пока. Разница между $O(n^2)$ и $O(2^n)$ для $n = 100$: 10 000 операций против $10^{30}$ - больше атомов в Земле. Класс **P** - это граница, отделяющая задачи, которые компьютер решит при жизни, от тех, на которые уйдут эпохи. И именно эта граница защищает каждый ваш банковский счёт.

**P** - класс задач разрешимости (ответ да/нет), которые решаются детерминированной машиной Тьюринга за полиномиальное время $O(n^k)$. Здесь $n$ - размер входа, $k$ - константа, не зависящая от $n$.

Почему именно полиномиальное время? Потому что полиномы **замкнуты относительно композиции**: полином от полинома - снова полином. Если один шаг алгоритма полиномиален и таких шагов полиномиально много - общее время полиномиально. Это делает класс P устойчивым и удобным для анализа.

Между $O(n^2)$ и $O(2^n)$ - пропасть. Для $n = 100$: $n^2 = 10\,000$ операций (мгновенно), а $2^n \approx 10^{30}$ (больше атомов в Земле). Bitcoin-майнинг намеренно построен на задаче из-за пределов P - это не баг, это архитектурное решение. Граница класса P - это граница практической вычислимости.

Класс NP и недетерминизм

А что если компьютер мог бы **угадывать**? Представьте машину, которая на каждом шаге «раздваивается» и пробует все варианты параллельно. Если хотя бы одна ветка находит решение - задача решена. Это **недетерминированная машина Тьюринга** (NTM). Класс задач, которые она решает за полиномиальное время, - это **NP**. Судоку 9×9 найти трудно, проверить - легко. TSP-маршрут для UPS - найти трудно, проверить длину - секунда. Это и есть NP.

**NP** (Nondeterministic Polynomial) - класс задач, решаемых недетерминированной машиной Тьюринга за полиномиальное время. Эквивалентное определение: NP - задачи, для которых **правильность предложенного решения** можно проверить за полиномиальное время.

**N в NP означает Nondeterministic, а не «Non-Polynomial»!** Критически важное различие. P ⊆ NP - каждая задача из P также в NP (детерминированная машина - частный случай недетерминированной). SAT-солверы в верификации чипов Intel, задача раскраски графа при распределении регистров компилятора, маршрутизация в логистике FedEx - всё это NP-задачи, которые решаются приближённо, потому что точное решение за полиномиальное время никто не нашёл.

Примеры задач из NP: задача коммивояжёра (TSP), раскраска графа, задача о рюкзаке, SAT. Для каждой из них предложенное решение можно **проверить** быстро, но **найти** его быстро - не умеем.

Верификация решений

Недетерминированная машина - абстракция. На практике удобнее другое определение NP: задача в NP, если для любого «да»-экземпляра существует **доказательство** (сертификат), которое можно **проверить** за полиномиальное время. Не найти решение - а проверить предложенное. Именно поэтому NP-задачи не бесполезны: их решения можно эффективно валидировать.

Альтернативное определение NP: задача L ∈ NP, если существует полиномиальный **верификатор** V(x, c), такой что: для каждого «да»-экземпляра x существует сертификат c полиномиальной длины, при котором V(x, c) = true. Верификатор работает за полиномиальное время от |x|.

Асимметрия NP: для «да»-ответа есть короткое доказательство (сертификат). Но для «нет»-ответа - не обязательно! Класс задач, где «нет»-ответ имеет короткое доказательство, называется **coNP**. Вопрос NP = coNP тоже открыт.

Сертификат

Сертификат (свидетель, witness) - это «подсказка», доказывающая что ответ - «да». Размер сертификата должен быть полиномиальным от размера входа. Для SAT - это набор значений переменных. Для задачи о клике - список вершин. Для гамильтонова цикла - сам цикл. Для доказательства теоремы - пошаговое обоснование. Разрыв между «проверить доказательство» и «найти доказательство» - это и есть суть P vs NP.

Формально: для задачи L ∈ NP существует полиномиальный верификатор V и полином p такие, что x ∈ L ⟺ ∃c: |c| ≤ p(|x|) и V(x, c) принимает. Сертификат c имеет длину не более p(|x|) - полиномиальную от входа.

Критически важно: сертификат должен быть **полиномиального размера**. Если бы допускались экспоненциальные сертификаты, то класс NP стал бы тривиальным (можно закодировать весь перебор в сертификат). Ограничение на длину - ключ к содержательности определения.

Итог. P - задачи, которые умеем решать быстро. NP - задачи, для которых решение можно быстро проверить (при наличии сертификата). Вопрос P = NP спрашивает: каждая ли задача, которую легко проверить, также легко решить? Интуиция говорит «нет» - проверить доказательство теоремы проще, чем его найти. Bitcoin стоит триллион долларов именно потому, что кто-то умный сделал правильную ставку на P ≠ NP.

Ключевые идеи

• **P** - задачи, решаемые за полиномиальное время $O(n^k)$; граница практической вычислимости
• **NP** - задачи, решения которых проверяются за полиномиальное время (Nondeterministic Polynomial, не Non-Polynomial)
• **P ⊆ NP** - каждая задача из P также в NP; вопрос в том, верно ли обратное
• **Сертификат** - доказательство «да»-ответа полиномиального размера, проверяемое за полиномиальное время
• NP-задачи - не теория. Это то, почему Bitcoin стоит триллион долларов, а RSA защищает интернет

Связанные темы

Классы P и NP - фундамент теории сложности вычислений:

• NP-полнота — Самые трудные задачи внутри NP - если одна в P, то все в P
• Классические NP-полные задачи — 3-SAT, клика, гамильтонов цикл - конкретные примеры NP-полных задач

Вопросы для размышления

• Почему большинство верит, что P ≠ NP? Какие аргументы «за» и «против»?
• Если бы P = NP, какие практические последствия это имело бы для криптографии, AI, математики?
• Задача PRIMES (проверка простоты) долго была в NP, но не доказано что в P. В 2002 алгоритм AKS показал PRIMES ∈ P. Какие ещё задачи могут «переехать» из NP в P?

Связанные уроки

• alg-01-big-o — Без понимания O-нотации невозможно разобраться в классах P и NP
• comp-01 — Теория сложности предполагает вычислимость: изучаем сложность только разрешимых задач
• ds-01-arrays — Структуры данных определяют сложность конкретных алгоритмов: дерево vs массив меняет O(n) на O(log n)
• dm-01 — NP-полные задачи формулируются через комбинаторные объекты дискретной математики: графы, множества, матрицы
• alg-34-approximation