Глава 7. Сводимость

познавания выглядит так: дано х; требуется определить, существует ли у такое, что х вместе с у удовлетворяют фиксированному условию R{x,у). Мы полагаем, что х и у — это коды некоторых математиче­ских объектов, т. е. слова в некотором алфавите Л.

Пусть задача распознавания связана указанным образом с задачей построения, пусть R{x, у)еР и полином р таков, что если существу­ет какое-то решение задачи построения, то существует и такое реше­ние у, что |у|^р(|х|). Тогда задача распознавания принадлежит NP в соответствии с определением 30.1, причем в качестве сертификата для х выступает это решение у.

В примерах из § 30 по рассмотренным задачам распознавания лег­ко восстанавливаются соответствующие им задачи построения (по­строить набор логических значений переменных; построить делитель данного числа; построить клику в графе, имеющую определенное ко­личество вершин, и т.д.). Для доказательства принадлежности клас­су NP задачи распознавания мы брали в качестве сертификата само решение соответствующей вычислительной задачи.

Такой выбор сертификатов в ряде доказательств, видимо, и служит причиной довольно распространенного представления, что класс Р образуют вычислительные задачи, решаемые за полиномиально огра­ниченное время, а класс NP—вычислительные задачи, для каждой из которых за полиномиально ограниченное время можно проверить, является ли данное слово у ее решением. На самом деле, конечно, в классы Р и NP входят только задачи распознавания, но упомяну­тое представление, будучи, строго говоря, неправильным, в извест­ной мере согласуется с реальным положением вещей.

Быстрый алгоритм распознавания наличия какого-то математиче­ского объекта, кодируемого словом из Л*, может в некоторых случа­ях позволить быстро решать и задачу фактического построения этого объекта. Проиллюстрируем это примером.

Пример 32.3. Мы знаем, что задача распознавания простоты нату­рального числа п принадлежит классу Р, — алгоритм Агравала, Кай-ала и Саксены (пример 22.2) имеет битовую сложность 0{т^1г), где т — битовая длина п. Вопрос о существовании полиномиального ал­горитма факторизации (разложения на простые множители) остается без ответа до сих пор при том, что алгоритмы факторизации имеют огромную важность, например, для криптографии. Вернемся в связи с этим вопросом к принадлежащей NP задаче, рассмотренной в при­мере 30.2: для заданных п, k е N⁺, к < п, выяснить, имеется ли у чис­ла п делитель I такой, что 1 < I s= к. Полиномиальный алгоритм реше-

Задачи

209

ния этой задачи тоже неизвестен, но можно показать, что открытие такого алгоритма—назовем его A — автоматически дало бы полино­миальный алгоритм факторизации (кстати сказать, существование A автоматически следовало бы из равенства Р = NP, если бы оно вдруг было доказано). Для этого можно воспользоваться бинарным поис­ком.

Пусть уже установлено, что n не имеет делителей, меньших n₁, где n₁ < n, и пусть n₂ таково, что n₁ < n₂ < n, и мы интересуемся наи­меньшим принадлежащим отрезку [n_г, n₂] простым множителем чис-

Гⁿ1+ⁿ21

ла n. Тогда, применяя Aкn, n₃, где n₃ = ——^—^£ , мы сузим диапазон поиска примерно вдвое: в зависимости от результата применения A мы перейдем от отрезка [n_ъ n₂] либо к отрезку [n_ъ n₃], либо к отрез­ку [n₃ + 1, n₂]. Первоначально же полагаем n_г = 2,n₂ = n. Применив алгоритм A не более m = [log₂(n + 1)1 раз, мы найдем наименьший простой множитель t числа n. Повторяем те же вычисления для

n' = t (32.2)

и т.д. Общее число простых множителей числа n с учетом их крат­ности ограничено сверху величиной log₂ n, и, значит, величиной m. Битовые затраты каждого деления (32.2) не превосходят Cm², где C — некоторая константа. Если битовая сложность алгоритма A есть O{m^d), то сложность описанного алгоритма факторизации будет до­пускать оценку O{m^d+2), т.е. этот алгоритм будет полиномиальным.

Задачи

145. Задача умножения квадратных булевых матриц линейно сводится к задаче построения транзитивно-рефлексивного замыка­ния (предполагается, что для сложностей рассматриваемых алгорит­мов построения транзитивно-рефлексивного замыкания выполнено T(Зn) = O(T(n))).

Указание. Пусть M_г и M₂—две булевы матрицы порядка n. Пусть X — бу­лева матрица порядка Зn:

0 0 M₂ . \0 0 0 /

Чему равны X²,X³? Воспользоваться формулой (23.1) для транзитивно-ре­флексивного замыкания.

210