Теорема Бермана — Форчуна


НЕТ ВОЙНЕ
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России
Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Лемма (1):

Язык является -полным тогда и только тогда, когда является -полным (то есть ).

Доказательство:

Пусть [math]L[/math] — [math]\mathrm{coNP}[/math]-полный. Тогда [math]L \in \mathrm{coNP}[/math] и .

Рассмотрим произвольный язык [math]L_1 \in \mathrm{NP}[/math]. Тогда . Так как [math]L[/math] — [math]\mathrm{coNP}[/math]-полный, то [math]\overline {L_1} \le L[/math], следовательно [math]L_1 \le \overline L[/math] (по лемме).

Получили, что и . Значит .

В обратную сторону доказательство аналогично.

Определение:

— булева формула .

Лемма (2):

.

Доказательство:

, то есть . Кроме того, в качестве сертификата используется , на котором . Значит . Тогда по лемме (1) .

Определение:

полином .

Теорема (Берман, Форчун):

.

Доказательство:

Пусть существует . Разрешим [math]\mathrm{TAUT}[/math] за полином.

Для начала напишем программу, разрешающую [math]\mathrm{TAUT}[/math]:

[math]check(\phi, i)[/math]:
    if [math]\phi=0[/math]
        return 0
    if [math]\phi=1[/math]
        return 1
    if [math]memo[\phi] \ne -1[/math]
        return [math]memo[\phi][/math]
    [math]memo[\phi] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)[/math]
    return [math]memo[\phi][/math]

Ответом будет [math]check(\phi, 1)[/math].

Так как и [math]S \in \mathrm{coNPC}[/math], то [math]\mathrm{TAUT} \le S[/math], то есть . Поэтому, если в предыдущей программе заменить все обращения к [math]memo[\phi][/math], на [math]memo[f(\phi)][/math], то полученная программа по-прежнему будет разрешать [math]\mathrm{TAUT}[/math].

Оценим необходимый размер [math]memo[/math]. Можно считать, что , где [math]n = |\phi|[/math], а [math]q[/math] — монотонно возрастающий полином. Тогда [math]|f(\phi)| \le q(n)[/math]. Так как [math]S \in \mathrm{SPARSE}[/math], то [math]|S \cap \Sigma^k| \le p(k)[/math], где [math]p[/math] — полином. Можно считать, что [math]p[/math] монотонно возрастает. Тогда размер [math]memo[/math] (число слов длины не более [math]q(n)[/math] в языке) можно оценить сверху: , где [math]r(n)[/math] — полином.

[math]check(\phi, i)[/math]:
    if [math]\phi=0[/math]
        exit 0
    if [math]\phi=1[/math]
        return 1
    if [math]memo[f(\phi)] \ne -1[/math]        //(1)
        return [math]memo[f(\phi)][/math]
    [math]memo[f(\phi)] \leftarrow check(\phi|_{x_i=0}, i+1) \wedge check(\phi|_{x_i=1}, i+1)[/math]        //(2)
    if [math]memo.size() \gt  r(n)[/math]
        exit [math]0[/math]
    return [math]memo[f(\phi)][/math]

Двоичное дерево, получающееся в результате рекурсивных вызовов модифицированной программы. Красным и желтым помечены узлы, в которых происходит обращение к элементу memo[j]. В красных узлах условие (1) ложно, в желтых — истинно.

Рассмотрим двоичное дерево, получающееся в результате рекурсивных вызовов данной программы.

Рассмотрим произвольный элемент [math]memo[j][/math]. Найдем, сколько раз условие [math](1)[/math] в ходе выполнения программы является ложным при обращении к элементу [math]memo[j][/math]. Найдем в дереве такой узел, в котором есть обращение к [math]memo[j][/math], а в его поддереве обращений к этому элементу нет, причем [math]memo[j] = -1[/math]. До этого момента количество обращений к [math]memo[j][/math] не превышает глубины найденного узла, что не превосходит высоты дерева, что не превосходит некоторого полинома [math]p'(n)[/math]. После этого момента условие [math](1)[/math] будет принимать истинное значение при обращении к [math]memo[j][/math]. Значит, в ходе выполнения программы условие [math](1)[/math] является ложным при обращении к [math]memo[j][/math] не более [math]p'(n)[/math] раз.

Так как всего в [math]memo[/math] не более [math]r(n)[/math] элементов, то суммарно за все время выполнения программы условие [math](1)[/math] принимает ложное значение не более [math]p''(n) = r(n) \cdot p'(n)[/math] раз, то есть [math]p''[/math] — полином. Отсюда следует, что присваивание [math](2)[/math] выполняется не более [math]p''(n)[/math] раз, а значит в дереве не более [math]p''(n)[/math] внутренних вершин. Значит всего в дереве не более [math]2 \cdot p''(n) + 1[/math] вершин, то есть данная программа работает за полиномиальное время.

Итого, данная программа разрешает за полиномиальное время. А так как , то , то есть , откуда .

См. также

Теорема Бермана — Форчуна

См. также

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты