Проблема перебора является, вероятно, самым главным открытым вопросом в области математической логики, философии математики и computer science, так что решить ее мечтают почти все.

Она фигурирует и в известном широкой публике списке «задач тысячелетия», за решение которых дают миллионные призы. (Проблема Пуанкаре, которую решил отказавшийся от приза Перельман, тоже была в этом списке.) Однако никто толком не знает, как к этой задаче подступиться. Неформально говоря, вопрос состоит в следующем: верно ли, что любую переборную задачу можно быстро решить?
Технически проблему перебора формулируют так: совпадают ли классы P и NP? Класс P — это те задачи, которые могут быть решены «быстро». А класс NP — это переборные задачи. Если P равно NP, то окажется, что все переборные задачи могут быть быстро решены. А если не равно, то не все.
Для начала надо объяснить, что такое переборная задача. Неформально можно сказать так: переборная задача — эта задача, в которой нужно найти объект, удовлетворяющий каким-то условиям. Причем эти условия легко проверить, но возможных кандидатов много. Пример такой задачи: есть ребус в виде кружков, соединенных линиями, и нужно расставить в кружках буквы А, Б и В (одну букву в каждом), причем требуется, чтобы кружки, соединенные линией, содержали разные буквы. Ясно, что когда буквы уже расставлены, то надо просто проверить условие для всех линий, это несложно. Зато вариантов расстановок очень много, и если перебирать их все, то это будет очень долго. Для этой задачи никакого существенно более быстрого способа пока не открыли. Существует такой способ или нет — в этом как раз и состоит проблема перебора.
Слова «быстро» и «долго» в предыдущем абзаце требуют уточнения, если мы хотим рассматривать проблему перебора как математическую задачу. Обычно их уточняют, используя какую-то абстрактную модель компьютера. Чаще всего для этого пользуются так называемыми машинами Тьюринга.
Эта теоретическая модель компьютера появилась еще до реальных компьютеров. В ней есть процессор, имеющий конечную память, и лента, разделенная на клетки. По командам процессора в эти клетки могут записываться (а потом из них считываться) символы. По своим вычислительным возможностям эта модель не уступает любым другим, и все, что можно запрограммировать для современных компьютеров, можно запрограммировать и на ней. Она используется для формального определения «числа шагов работы программы»: считаются шаги машины Тьюринга, выполняемые по этой программе. Вместо этого можно было бы использовать и другие формально определенные модели вычислений, просто исторически Тьюринг был первым, кто рассмотрел модель вычисления, где можно считать шаги.
Читать дальше: http://postnauka.ru/faq/43795