Теперь рассмотрим, какие показатели производительности демонстрируют алгоритмы DPLL и WalkSAT на практике. Нас особенно интересуют трудные задачи, поскольку легкие могут быть решены с помощью любого старого алгоритма. В главе 5 мы ознакомились с некоторыми удивительными открытиями в области решения задач определенного типа. Например, задача с п ферзями (которая когда-то рассматривалась как чрезвычайно сложная) при ее решении с помощью алгоритмов поиска с возвратами оказалась тривиально простой для методов локального поиска, таких как метод с минимальными конфликтами. Это связано с тем, что решения этой задачи распределены в пространстве присваиваний очень плотно и для любого начального присваивания гарантируется, что решение находится недалеко. Таким образом, задача с п ферзями является простой потому, что она недостаточно ограниченна.

Если речь идет о решении задач проверки выполнимости, представленных в конъюнктивной нормальной форме, то среди них недостаточно ограниченными можно считать такие задачи, которые содержат относительно немного выражений, ограничивающих значения переменных. Например, ниже представлено выработанное случайным образом12 высказывание в форме 3-CNF с пятью символами и пятью выражениями.

Моделями этого высказывания являются 16 из 32 возможных вариантов присваивания, поэтому в среднем для поиска модели потребуются только две случайно выбранных гипотезы.

Так где же найти сложные задачи? Можно предположить, что если количество выражений будет увеличено, притом что количество символов останется постоянным, то задача станет более ограниченной и поиск решений окажется более затруднительным. Допустим, что m — количество выражений, а п — количество символов. На рис. 7.8, а показана вероятность того, что случайно сформированное высказывание в форме 3-CNF является выполнимым, как функция от отношения "выражение/символ", т/п, при постоянном значении п, равном 50. Как и следовало ожидать, при малых значениях т/п эта вероятность близка к 1, а при больших значениях т/п вероятность близка к 0. На кривой вероятности начинается довольно резкий спад приблизительно после достижения значения m/n=4.3. Высказывания в форме CNF, приближающиеся к этой критической точке, можно назвать "почти выполнимыми", или "почти невыполнимыми". Можно ли считать, что именно здесь находятся трудные задачи?