Технически проблему перебора формулируют так: совпадают ли классы P и NP? Класс P — это те задачи, которые могут быть решены «быстро». А класс NP — это переборные задачи. Если P равно NP, то окажется, что все переборные задачи могут быть быстро решены. А если не равно, то не все.
Определение переборной задачи
Для начала надо объяснить, что такое переборная задача. Неформально можно сказать так: переборная задача — эта задача, в которой нужно найти объект, удовлетворяющий каким-то условиям. Причем эти условия легко проверить, но возможных кандидатов много. Пример такой задачи: есть ребус в виде кружков, соединенных линиями, и нужно расставить в кружках буквы А, Б и В (одну букву в каждом), причем требуется, чтобы кружки, соединенные линией, содержали разные буквы. Ясно, что когда буквы уже расставлены, то надо просто проверить условие для всех линий, это несложно. Зато вариантов расстановок очень много, и если перебирать их все, то это будет очень долго. Для этой задачи никакого существенно более быстрого способа пока не открыли. Существует такой способ или нет — в этом как раз и состоит проблема перебора.
Более формальное определение
Слова «быстро» и «долго» в предыдущем абзаце требуют уточнения, если мы хотим рассматривать проблему перебора как математическую задачу. Обычно их уточняют, используя какую-то абстрактную модель компьютера. Чаще всего для этого пользуются так называемыми машинами Тьюринга.
Эта теоретическая модель компьютера появилась еще до реальных компьютеров. В ней есть процессор, имеющий конечную память, и лента, разделенная на клетки. По командам процессора в эти клетки могут записываться (а потом из них считываться) символы. По своим вычислительным возможностям эта модель не уступает любым другим, и все, что можно запрограммировать для современных компьютеров, можно запрограммировать и на ней. Она используется для формального определения «числа шагов работы программы»: считаются шаги машины Тьюринга, выполняемые по этой программе. Вместо этого можно было бы использовать и другие формально определенные модели вычислений, просто исторически Тьюринг был первым, кто рассмотрел модель вычисления, где можно считать шаги.
Соответственно, когда мы определяем класс P (класс «быстро решаемых» задач), то требуем, чтобы число шагов машины Тьюринга, решающей такую задачу, было невелико: при обработке входных данных из n битов число шагов должно быть ограничено некоторой степенью числа n (полиномом). Поэтому задачи из P называют задачами, разрешимыми на полиномиальное время, буква P в названии как раз происходит от polynomial time (полиномиальное время).
Класс переборных задач называют NP — в первых работах он определялся в терминах так называемых недетерминированных машин Тьюринга (Non-deterministic Polynomial-Time Turing machines, отсюда N и P), но попытки объяснить, что это такое и какое отношение они имеют к переборным задачам, только запутают дело. Проще сказать, что в таких задачах мы интересуемся вопросом о наличии объекта полиномиального размера, обладающего некоторым полиномиально проверяемым свойством.
Практическое значение проблемы перебора
Проблема перебора важна прежде всего для современной криптографии. Если обнаружится, что есть быстрый способ решения переборных задач, то разрушится вся современная технология криптографии с открытым ключом, позволяющая наладить предположительно безопасный обмен информацией между собеседниками, которые не договорились заранее о каком-то секретном ключе, известном только им. Такой «взлом» приведет к серьезному экономическому кризису, потому что в нынешнем мире на криптографии с открытым ключом очень многое завязано (все стандартные протоколы защищенной передачи информации именно таковы).
Во избежание путаницы стоит отметить, что Тьюринг известен также своими криптографическими работами в годы Второй мировой войны, но они не имеют отношения к машинам Тьюринга в том смысле, в каком их обычно упоминают, а также к современной криптографии. Тьюринг участвовал в построении машин для расшифровки сообщений немецких военных, и это сыграло большую роль в ходе войны. Эти машины тоже можно было бы назвать машинами Тьюринга, но это совсем другие машины.
Конечно, от положительного решения проблемы перебора (то есть от быстрого алгоритма решения переборных задач), помимо вреда для криптографии, можно ожидать и пользу: важные практические задачи можно будет быстро решать. Правда, это будет зависеть от того, насколько практичным окажется этот самый быстрый алгоритм. Теоретическое понятие быстрого алгоритма (алгоритм, работающий за полиномиальное время) само по себе такой практичности не гарантирует, хотя большая часть придуманных теоретических быстрых алгоритмов оказывается и на практике полезной. Если появится действительно практичный алгоритм для переборных задач, то это найдет много применений и хотя бы частично скомпенсирует негативный эффект для криптографии.
Теперь о возможных последствиях решения проблемы в отрицательную сторону (доказательства невозможности быстрого решения переборных задач). Можно ожидать, что в таком доказательстве появятся какие-то новые сильные методы анализа сложности задач, поскольку существующие не помогают. Это будет важнейшим продвижением, о котором все мечтают последние сорок лет, — в частности, это даст надежду на построение доказуемо надежных систем криптографии с открытым ключом.
История исследования проблемы перебора
Алгоритмы решения переборных задач искали самые разные люди, потому что очень многие практические задачи попадают в этот класс. В начале 1970-х годов было замечено, что самые разные переборные задачи эквивалентны друг другу и универсальны: если кто-то придумает быстрый алгоритм решения одной из них, то с его помощью можно будет быстро решать любую другую переборную задачу. Это поняли независимо Стивен Кук (Stephen Arthur Cook) и Леонид Левин (Leonid A. Levin). Тем самым оказалось, что мы во многих случаях реально имеем дело с одной и той же проблемой, которую по-русски называют проблемой перебора (по-английски говорят обычно P vs NP question). Статья Кука вышла в 1971 году (он сделал доклад на одной из самых известных конференций по теоретической информатике), статья Левина вышла только в 1973 году в журнале «Проблемы передачи информации» на русском языке, так что стала известной позже. (Заметим в скобках, что защиту диссертации Левина — тоже очень важной работы, но на другую тему — провалили в Новосибирске. Вскоре после этого Левин эмигрировал из СССР и написал много других интересных работ уже в качестве американского ученого.)
На данный момент получено множество интересных результатов, так или иначе связанных с проблемой перебора, но сказать, что достигнут какой-то прогресс и надо идти дальше по известному пути, никто не может. Время от времени, как и в случае с теоремой Ферма, появляются работы, где авторы утверждают, что они ее решили, но пока что ничего из этого не подтвердилось.
Проблема перебора и квантовый компьютер
Сейчас много говорят о квантовых компьютерах (и кое-кто даже надеется, что их можно будет реально построить в не слишком отдаленном будущем). Сможет ли квантовый компьютер обойти проблему перебора? Если говорить не о квантовом компьютере, а о той его математической модели, которая есть сейчас, то ситуация такова: некоторые переборные задачи, например разложение многозначного целого числа на простые множители, квантовые компьютеры смогут решать быстро.
Разложение на множители важно, потому что именно на нем основаны используемые сейчас алгоритмы криптографии. В этом смысле квантовые компьютеры скорее представляют собой угрозу: если они появятся, то с криптографией придется что-то делать, нынешние криптографические алгоритмы можно будет «взломать». Однако уверенности в том, что квантовые компьютеры действительно удастся построить в соответствии с имеющимися математическими моделями, ни у кого нет.
Что касается произвольных переборных задач, то быстрые алгоритмы их решения пока что неизвестны даже для квантовых компьютеров. Не исключено, что квантовые алгоритмы могут быстро разлагать числа на множители, но не могут решать другие задачи из класса NP. Это будет означать, в частности, что задача разложения неуниверсальна в классе NP (не самая трудная в этом классе).
