Научная Сеть >> М.Н. Вялый "Сложность вычислительных задач"

Наука >> Математика >> Математическое образование | Популярные статьи

Next: 6.4. 3-раскраска Up: 6. Примеры NP-полных задач Previous: 6.2. Разрешимость системы уравнений Contents: Содержание

6.3. Целочисленное линейное программирование (ЦЛП)

Теперь разберем задачу из примера 2, т. е. разрешимость системы линейных диофантовых уравнений в неотрицательных числах.

Замечание 4. Название "линейное программирование" относится к задачам минимизации линейной функции на множестве решений системы линейных неравенств. Слово "целочисленное" указывает, что учитываются только те решения, для которых значения всех переменных - целые. С точностью до полиномиальных сводимостей задача разрешимости системы (4) эквивалентна задаче ЦЛП. Доказательство этого оставляется читателю в качестве упражнения.

Теорема 3. Задача проверки разрешимости системы линейных уравнений в неотрицательных целых числах $\ensuremath{\mathrm {NP}}$ -полна.

Как и в предыдущих случаях, нам необходимо доказать два утверждения: что эта задача принадлежит классу $\ensuremath{\mathrm {NP}}$ и что к ней сводятся все задачи из $\ensuremath{\mathrm {NP}}$ . Но теперь нетривиальны оба утверждения. Естественно пытаться доказывать принадлежность $\ensuremath{\mathrm {NP}}$ следующим образом: пусть Советник сообщит решение, а Исполнитель его проверит. Но тогда решение должно состоять из не слишком больших чисел, чтобы Исполнитель мог проверить выполнение равенств (4) за полиномиальное время.

Оказывается, что так оно и есть: из разрешимости системы (4) следует существование не слишком длинных решений. Опишем кратко идею доказательства.

Основная используемая оценка - это оценка величины определителя матрицы через длину ее описания. Обозначим длину записи матрицы (кодировка указана в примере 1) через . Тогда

$\begin{displaymath} \vert\det A\vert\leq\prod_{i,j=1}^{n}(1+\vert a_{ij}\vert)\leq 2^s. \end{displaymath}$ (10)

Первое неравенство следует непосредственно из определения $\det A$ , второе - из того, что запись числа

требует не менее $1+\log\vert a\vert\geq\log(1+\vert a\vert)$ битов.

Множество вещественных решений системы (4) является полиэдром - пересечением конечного числа полупространств. Хорошо известная теорема выпуклой геометрии утверждает, что любая точка полиэдра является выпуклой комбинацией его крайних точек и точек на его крайних лучах. Крайние точки полиэдра, задаваемого системой (4), являются решениями систем линейных уравнений вида

$\begin{displaymath} \left\{ \begin{aligned} Ax&=b, [3pt] x_i&=0, \quad i\in S, \end{aligned}\right. \end{displaymath}$ (11)

для каких-то подмножеств $S\subseteq \{1,\dots, n\}$ . Координаты этих точек по правилу Крамера являются отношениями миноров расширенной матрицы этой системы. В силу оценки (10) они не превосходят $2^{s+n^2+n}$ (в показателе написана максимально возможная длина описания минора расширенной матрицы).

Направляющие векторы крайних лучей - ненулевые (без ограничения общности, целочисленные) решения однородных систем вида

$\begin{displaymath} \left\{ \begin{aligned} Ax&=0,\\ x_i&=0, \quad i\in S, [3pt] \end{aligned}\right. \end{displaymath}$ (12)

поэтому можно считать, что для их координат выполняются те же неравенства.

Обозначим крайние точки полиэдра $x^{(1)},\dots,x^{(N)}$ , направляющие векторы крайних лучей $y^{(1)},\dots,y^{(M)}$ . Пусть у системы (4) есть целочисленное решение . Тогда его можно записать в виде

$\begin{displaymath} x= \sum_{i=1}^{N}\lambda_i x^{(i)}+\sum_{j=1}^{M} \mu_jy^{(j... ...\sum_{j=1}^{M} (\mu_j-\lfloor \mu_j\rfloor)y^{(j)}+ y^{(\mu)}, \end{displaymath}$ (13)

где $\lambda_i,\mu_j\geq0$ , $\sum_{i=1}^{N}\lambda_i=1$ , все координаты вектора $x^{(\lambda)}$ ограничены $2^{s+n^2+n}$ , а вектор $y^{(\mu)}$ - целочисленный. Но тогда и вектор $x-y^{(\mu)}$ является целочисленным решением системы (4), а его координаты не превосходят $(M+1)2^{s+n^2+n}$ . Заметим, что

заведомо не превосходит

(а если вспомнить теорему Каратеодори, то $M\leq n$ ).

Итак, мы доказали, что для разрешимой в неотрицательных целых числах системы найдется и такое решение, длина записи которого (мы грубо оценили как ). Отсюда следует принадлежность этой задачи классу $\ensuremath{\mathrm {NP}}$ .

Для доказательства $\ensuremath{\mathrm {NP}}$ -полноты задачи разрешимости системы линейных уравнений в неотрицательных целых числах сведем к ней задачу 3-КНФ. Построим по 3-КНФ систему линейных уравнений в неотрицательных целых числах. Булевой переменной из 3-КНФ сопоставим целочисленную неотрицательную переменную , отрицанию переменной - , дизъюнкции - переменную . Каждой дизъюнкции $D= X_j\vee X_k \vee X_m$ ( - литералы) сопоставим также уравнение , в котором , , - переменные, сопоставленные литералам дизъюнкции.

Искомая система содержит для всех уравнения , а также все уравнения, сопоставленные дизъюнкциям из КНФ. Очевидно, что выполнимость 3-КНФ равносильна совместности такой системы.

МЦНМО

Написать комментарий