На этом шаге мы рассмотрим понятие переборной задачи (задачи решаемой с помощью полного перебора).
Положим, у нас имеется множество S из n элементов. Нам требуется отыскать какое-либо его подмножество, обладающее определенным свойством. Это можно сформулировать так: дан предикат (утверждение) P(A), определенный на множестве 2S всех подмножеств множества S, т. е. A∈2S, истинный на одних подмножествах (быть может, только на одном) и ложный на других (быть может, на всех). Пример: множество S состоит из и различных целых чисел {1, 3, 4, 7, 8, 14, 20, 23, 25, 28}; предикат P(A) = {множество A содержит только четные числа}. В этом случае P({3, 7, 14}) = false, P({4, 20, 28}) = true.
Утверждение P называют еще свойством множества A. Для конкретного множества A легко выяснить, обладает ли оно свойством P. Не найти множество, обладающее свойством P зачастую можно только, проверив для всех A∈2S, выполняется ли P(A). Например, для упомянутого множества S целых чисел можно написать уравнение P1(Х) = true, где P1(Х) = {сумма чисел, входящих в X, равна 32}. Это известная задача о рюкзаке, в которой требуется найти подмножество заданного множества натуральных чисел, причем сумма чисел, входящих в подмножество, должна быть равна другому заданному числу m. Найти решение этого уравнения, т. е. найти подходящее множество X можно в общем случае только перебором и проверкой вариантов. Каждое подмножество может быть описано характеристической функцией c: S -> {0,1} так, что сi = 1, если i-й элемент множества S принадлежит X и ci = 0 в противном случае. Для решения задачи в худшем случае перебрать нужно все варианты, а их 2n. В настоящее время не известно никакого способа вычисления X (под термином "вычисление" мы понимаем альтернативу перебору).
Теперь можно дать более формальное определение задачи, решаемой методом перебора.
Переборная задача - это задача с параметром сложности исходных данных n, решение которой может быть выражено в виде совокупности значений c1, с2, ..., cn , параметров x1, x2, ..., xn, каждый из которых может принимать только конечное число значений, причем формулировка задачи содержит явное указание на то, как вычислить (проверить), является ли данный набор {ci} удовлетворительным (допустимым) решением задачи, но не известно (или не существует) никакого способа вычислить значения {ci} по формуле или с помощью алгоритма полиномиальной сложности.
Разумеется, переборная задача имеет экспоненциальную сложность при вычислениях на однопроцессорной машине.
На следующем шаге мы рассмотрим понятие задачи распознавания.
