Великая задача, которая нас в данный момент интересует, заключается в поиске ответа на более фундаментальный вопрос. Существуют ли сложные задачи? Могут ли все задачи оказаться простыми, если, конечно, приложить достаточно ума и сообразительности? На самом деле здесь есть одна тонкость, потому что мы уже видели одну несомненно сложную задачу: распечатку списка всех n-значных двоичных чисел. Я уже упоминал о том, что это глупый пример: сложность заключается не в расчетах, а в простой монотонной работе по распечатке очень длинного ответа. Нам известно, что никакие уловки здесь не помогут, поскольку ответ будет таким длинным по определению. Если бы он был короче, он не был бы ответом.

Чтобы поставить вопрос разумным образом, необходимо исключить подобные тривиальные примеры. Для этого введем еще один класс алгоритмов, класс NP. Это не класс не-P — это класс алгоритмов, работа которых занимает недетерминированное полиномиальное время. В переводе с математического это означает, что, сколько бы времени ни требовалось алгоритму на поиск ответа, убедиться в верности этого ответа мы можем за полиномиальное время. Задача поиска ответа может быть сложной, но если ответ найден, то существует простой способ проверки его корректности.

Слово «недетерминированный» здесь используется потому, что существует возможность решить NP-задачу при помощи просто вдохновенной догадки. Сделав это, можно проверить и убедиться, что ответ действительно верен (или нет). К примеру, если задача заключается в разложении на простые множители числа 11 111 111 111, то вы можете предположить, что одним из множителей является простое число 21 649. Пока это всего лишь догадка, однако ее легко проверить: достаточно разделить исходное число на 21 649 и посмотреть, что получится. Частное равняется 513 239 точно, без остатка. Таким образом, ваша догадка оказалась верной. А если бы я догадался, что делителем должно быть 21 647 — тоже простое число, то деление привело бы к ответу 513 286 с остатком 9069. Таким образом, догадка оказалась бы неверной.

В данном случае правильное предположение можно сделать только чудом или при помощи обмана (я, кстати, прежде чем высказывать «предположение», разложил 11 111 111 111 на простые множители). Но, по существу, мы хотим именно этого. Если бы наша догадка не была чудесной, то можно было бы превратить алгоритм класса NP в алгоритм класса P очень простым способом: нужно было бы делать предположения одно за другим до тех пор, пока одно из них не оказалось бы верным. Мой пример позволяет увидеть, что так не получится: понадобилось бы слишком много попыток. В самом деле, то, что мы пытаемся делать, это всего лишь «пробное деление» на все возможные простые числа до тех пор, пока одно из них не сработает. Из главы 2 мы знаем, что это далеко не лучший способ искать делители.

Класс NP исключает глупые примеры вроде уже упоминавшегося очень длинного списка. Если кто-то в порыве вдохновения выдаст список всех n-значных двоичных чисел, то экспоненциальное время уйдет не только на то, чтобы их распечатать, но и на то, чтобы их прочесть, и еще больше времени — на то, чтобы проверить список. Это потребовало бы громадных корректорских усилий. Класс P определенно входит составной частью в класс NP.