Задачи

Пусть

Покажите, что $\operatorname {MODEXP} \in \mathrm{P}$. (Заметим, что самый очевидный алгоритм не работает за полиномиальное время. Подсказка: сначала попробуйте случай, когда $b$ — степень двойки.)

Перестановкой множества $\left\{ 1, \ldots , k\right\}$ называется взаимно однозначная функция этого множества на себя. Когда $p$ — перестановка, $p^{t}$ означает композицию $p$ с самой собой $t$ раз. Пусть

Покажите, что PERM-POWER $\in \mathrm{P}$. (Заметим, что самый очевидный алгоритм не работает за полиномиальное время. Подсказка: сначала попробуйте случай, когда $t$ — степень двойки.)

Покажите, что P замкнут относительно операции звезды. (Подсказка: используйте динамическое программирование. На входе $y=y_{1} \cdots y_{n}$, где $y_{i} \in \Sigma$, постройте таблицу, указывающую для каждой пары $i \leq j$, принадлежит ли подстрока $y_{i} \cdots y_{j}$ языку $A^{*}$ для некоторого $A \in \mathrm{P}$.)

ᴬ Покажите, что NP замкнут относительно операции звезды.

Пусть UNARY-SSUM — задача о сумме подмножества, в которой все числа представлены в унарной системе счисления. Почему доказательство NP-полноты для SUBSET-SUM не показывает, что UNARY-SSUM NP-полна? Покажите, что UNARY-SSUM $\in \mathrm{P}$.

Покажите, что если $\mathrm{P}=\mathrm{NP}$, то каждый язык $A \in \mathrm{P}$, кроме $A=\emptyset$ и $A=\Sigma^{*}$, NP-полон.

• Покажите, что PRIMES $=\left\{ m \mid m\text{ — простое число в двоичной записи}\right\} \in \mathrm{NP}$. (Подсказка: при $p>1$ мультипликативная группа $Z_{p}^{*}=\left\{ x \mid x\text{ взаимно просто с }p\text{ и }1 \leq x<p\right\}$ является циклической и имеет порядок $p-1$ тогда и только тогда, когда $p$ простое. Вы можете использовать этот факт без обоснования. Более сильное утверждение PRIMES $\in \mathrm{P}$ в настоящее время известно как истинное, но доказать его сложнее.)

Мы обычно полагаем, что PATH не является NP-полной. Объясните, на чём основано это убеждение. Покажите, что доказательство того, что PATH не NP-полна, доказало бы $\mathrm{P} \neq \mathrm{NP}$.

Пусть $G$ обозначает неориентированный граф. Также пусть

и

Пусть DOUBLE-SAT $=\left\{ \langle \phi \rangle \mid \phi \text{ имеет хотя бы два выполняющих означивания}\right\}$. Покажите, что DOUBLE-SAT NP-полна.

ᴬ Пусть HALF-CLIQUE $=\left\{ \langle G\rangle \mid G\text{ — неориентированный граф, имеющий полный подграф не менее чем на }m / 2\text{ вершинах, где }m\text{ — число вершин }G\right\}$. Покажите, что HALF-CLIQUE NP-полна.

Пусть $C N F_{k}=\left\{ \langle \phi \rangle \mid \phi \text{ — выполнимая кнф-формула, в которой каждая переменная встречается не более чем в }k\text{ местах}\right\}$.

Пусть $C N F_{\mathrm{H}}=\left\{ \langle \phi \rangle \mid \phi \text{ — выполнимая кнф-формула, в которой каждый дизъюнкт содержит произвольное число литералов, но не более одного отрицательного литерала}\right\}$. Покажите, что $C N F_{\mathrm{H}} \in \mathrm{P}$.

Пусть $\phi$ — 3кнф-формула. $\neq$-означиванием переменных $\phi$ называется такое означивание, при котором каждый дизъюнкт содержит два литерала с неравными истинностными значениями. Иными словами, $\neq$-означивание выполняет $\phi$, не присваивая значение «истина» всем трём литералам ни в одном дизъюнкте.

Разрезом в неориентированном графе называется разбиение вершин $V$ на два непересекающихся подмножества $S$ и $T$. Размером разреза называется число рёбер, у которых один конец лежит в $S$, а другой — в $T$. Пусть

Покажите, что MAX-CUT NP-полна. Вы можете использовать результат задачи 7.26. (Подсказка: покажите, что $\neq SAT \leq_{\mathrm{P}}$ MAX-CUT. Гаджет переменной $x$ — это совокупность из $3c$ вершин, помеченных $x$, и ещё $3c$ вершин, помеченных $\bar{x}$, где $c$ — число дизъюнктов. Все вершины, помеченные $x$, соединены со всеми вершинами, помеченными $\bar{x}$. Гаджет дизъюнкта — это треугольник из трёх рёбер, соединяющих три вершины, помеченные литералами, входящими в дизъюнкт. Не используйте одну и ту же вершину более чем в одном гаджете дизъюнкта. Докажите, что это сведение работает.)

Вам даны коробка и набор карточек, как показано на следующем рисунке. Из-за штырьков в коробке и вырезов на карточках каждую карточку можно вложить в коробку одним из двух способов. Каждая карточка содержит два столбца отверстий, часть из которых может быть не пробита. Головоломка решена, если все карточки размещены в коробке так, чтобы полностью закрыть дно коробки (то есть каждая позиция отверстия перекрыта хотя бы одной карточкой, у которой в этом месте нет отверстия). Пусть $\operatorname {PUZZLE}=\left\{ \left\langle c_{1}, \ldots , c_{k}\right\rangle \mid \text{каждая } c_{i} \text{ представляет карточку, и для этого набора карточек существует решение}\right\}$. Покажите, что PUZZLE NP-полна.

Раскраской графа называется присвоение цветов его вершинам так, чтобы никакие две смежные вершины не получили одинаковый цвет. Пусть

Покажите, что 3COLOR NP-полна. (Подсказка: используйте следующие три подграфа.)

Пусть SET-SPLITTING $=\left\{ \langle S, C\rangle \mid S \text{ — конечное множество, а } C=\left\{ C_{1}, \ldots , C_{k}\right\} \text{ — набор подмножеств } S, \text{ при некотором } k>0, \text{ такой что элементы } S \text{ можно раскрасить в красный или синий цвет так, чтобы ни одно } C_{i} \text{ не оказалось целиком одного цвета}\right\}$. Покажите, что SET-SPLITTING NP-полна.

Рассмотрим следующую задачу составления расписания. Вам даны список экзаменов $F_{1}, \ldots , F_{k}$, которые нужно расписать, и список студентов $S_{1}, \ldots , S_{l}$. Каждый студент сдаёт некоторое заданное подмножество этих экзаменов. Нужно распределить экзамены по слотам так, чтобы ни одному студенту не пришлось сдавать два экзамена в одном слоте. Задача состоит в том, чтобы определить, существует ли такое расписание, использующее только $h$ слотов. Сформулируйте эту задачу как язык и покажите, что этот язык NP-полон.

Эта задача навеяна однопользовательской игрой «Сапёр» (Minesweeper), обобщённой на произвольный граф. Пусть $G$ — неориентированный граф, каждая вершина которого либо содержит одну скрытую мину, либо пуста. Игрок выбирает вершины одну за другой. Если игрок выбирает вершину, содержащую мину, он проигрывает. Если игрок выбирает пустую вершину, он узнаёт число соседних вершин, содержащих мины. (Соседней называется вершина, соединённая с выбранной ребром.) Игрок выигрывает, если и когда все пустые вершины оказываются выбраны. В задаче согласованности мин вам дан граф $G$ вместе с числами, которыми помечены некоторые вершины $G$. Нужно определить, возможно ли такое размещение мин на оставшихся вершинах, чтобы у любой вершины $v$, помеченной числом $m$, было ровно $m$ соседних вершин, содержащих мины. Сформулируйте эту задачу как язык и покажите, что она NP-полна.

ᴬ В следующей игре-пасьянсе вам дана доска размера $m \times m$. На каждой из её $m^{2}$ позиций лежит либо синий камень, либо красный камень, либо ничего. Вы играете, снимая камни с доски, пока в каждом столбце не останутся камни только одного цвета, а в каждой строке останется хотя бы один камень. Вы выигрываете, если добиваетесь этой цели. Выигрыш может быть возможен или невозможен в зависимости от начальной конфигурации. Пусть SOLITAIRE $=\left\{ \langle G\rangle \mid G\text{ — выигрышная конфигурация игры}\right\}$. Докажите, что SOLITAIRE NP-полна.

Вспомним, что при обсуждении тезиса Чёрча-Тьюринга мы ввели язык $D=\left\{ \langle p\rangle \mid p\text{ — многочлен от нескольких переменных, имеющий целочисленный корень}\right\}$. Мы утверждали, но не доказывали, что $D$ неразрешим. В этой задаче требуется доказать другое свойство $D$ — а именно, что $D$ NP-труден. Задача называется NP-трудной, если все задачи из NP сводятся к ней за полиномиальное время, хотя сама она может не принадлежать NP. Таким образом, вам нужно показать, что все задачи из NP сводятся к $D$ за полиномиальное время.

Подмножество вершин графа $G$ называется доминирующим множеством, если каждая другая вершина $G$ смежна с некоторой вершиной этого подмножества. Пусть

Покажите, что эта задача NP-полна, приведя сведение от VERTEX-COVER.

• Покажите, что следующая задача NP-полна. Вам дано множество состояний $Q=\left\{ q_{0}, q_{1}, \ldots , q_{l}\right\}$ и набор пар $\left\{ \left(s_{1}, r_{1}\right), \ldots ,\left(s_{k}, r_{k}\right)\right\}$, где $s_{i}$ — попарно различные строки над $\Sigma =\left\{ 0,1\right\}$, а $r_{i}$ — элементы $Q$ (не обязательно различные). Определите, существует ли ДКА $M=\left(Q, \Sigma , \delta , q_{0}, F\right)$, для которого $\delta \left(q_{0}, s_{i}\right)=r_{i}$ при каждом $i$. Здесь $\delta (q, s)$ — состояние, в которое переходит $M$ после чтения $s$, начиная с состояния $q$. (Заметим, что $F$ здесь неважно.)

Пусть $U=\left\{ \left\langle M, x, \#^{t}\right\rangle \mid \text{НМТ } M \text{ допускает } x \text{ не более чем за } t \text{ шагов хотя бы на одной ветви}\right\}$. Заметим, что от $M$ не требуется останавливаться на всех ветвях. Покажите, что $U$ NP-полна.

• Покажите, что если $\mathrm{P}=\mathrm{NP}$, то существует алгоритм, работающий за полиномиальное время, который по выполнимой булевой формуле выдаёт выполняющее означивание. (Примечание: алгоритм, который от вас требуется, вычисляет функцию; но NP содержит языки, а не функции. Предположение $\mathrm{P}=\mathrm{NP}$ влечёт, что SAT принадлежит P, так что проверка выполнимости разрешима за полиномиальное время. Но предположение не говорит, как именно выполняется эта проверка, и она может не выявлять выполняющие означивания. Вы должны показать, что их всё равно можно найти. Подсказка: используйте тест на выполнимость многократно, чтобы находить означивание бит за битом.)

• Покажите, что если $\mathrm{P}=\mathrm{NP}$, то можно раскладывать целые числа на множители за полиномиальное время. (См. примечание в задаче 7.38.)

ᴬ Покажите, что если $\mathrm{P}=\mathrm{NP}$, то существует алгоритм, работающий за полиномиальное время, который по неориентированному графу находит наибольшую клику, содержащуюся в этом графе. (См. примечание в задаче 7.38.)

В доказательстве теоремы Кука-Левина окном называется прямоугольник клеток размера $2 \times 3$. Объясните, почему доказательство не сработало бы, если бы мы использовали окна $2 \times 2$.

• Рассмотрим алгоритм MINIMIZE, который принимает на входе ДКА $M$ и выдаёт ДКА $M^{\prime }$. MINIMIZE = «На входе $\langle M\rangle$, где $M=\left(Q, \Sigma , \delta , q_{0}, A\right)$ — ДКА:

1. Удалить все состояния $M$, недостижимые из начального состояния. 2. Построить следующий неориентированный граф $G$, вершинами которого являются состояния $M$. 3. Провести в $G$ ребро, соединяющее каждое допускающее состояние с каждым недопускающим. Добавить дополнительные рёбра следующим образом. 4. Повторять, пока в $G$ не перестанут добавляться новые рёбра: 5. Для каждой пары различных состояний $q$ и $r$ автомата $M$ и каждого $a \in \Sigma$: 6. Добавить ребро $(q, r)$ в $G$, если $(\delta (q, a), \delta (r, a))$ — ребро $G$. 7. Для каждого состояния $q$ пусть $[q]$ — совокупность состояний $[q]=\left\{ r \in Q \mid \text{ ни одно ребро не соединяет }q\text{ и }r\text{ в }G\right\}$. 8. Построить новый ДКА $M^{\prime }=\left(Q^{\prime }, \Sigma , \delta^{\prime }, q_{0}{ }^{\prime }, A^{\prime }\right)$, где $Q^{\prime }=\left\{ [q] \mid q \in Q\right\}$ (если $[q]=[r]$, в $Q^{\prime }$ входит только одно из них), $\delta^{\prime }([q], a)=[\delta (q, a)]$ для каждого $q \in Q$ и $a \in \Sigma$, $q_{0}{ }^{\prime }=\left[q_{0}\right]$, а $A^{\prime }=\left\{ [q] \mid q \in A\right\}$. 9. Вывести $\left\langle M^{\prime }\right\rangle$.»

Для кнф-формулы $\phi$ с $m$ переменными и $c$ дизъюнктами покажите, что можно построить за полиномиальное время НКА с $O(c m)$ состояниями, допускающий все невыполняющие означивания, представленные в виде булевых строк длины $m$. Сделайте вывод, что из $\mathrm{P} \neq \mathrm{NP}$ следует, что НКА нельзя минимизировать за полиномиальное время.

• 2кнф-формула — это конъюнкция дизъюнктов, каждый из которых является дизъюнкцией не более чем двух литералов. Пусть $2 S A T=\left\{ \langle \phi \rangle \mid \phi \text{ — выполнимая 2кнф-формула}\right\}$. Покажите, что $2 S A T \in \mathrm{P}$.

Измените алгоритм распознавания контекстно-свободных языков из доказательства теоремы 7.16 так, чтобы получить алгоритм за полиномиальное время, строящий дерево вывода для строки по данным строке и КС-грамматике, если эта грамматика порождает данную строку.

Будем говорить, что две булевы формулы эквивалентны, если у них одинаковое множество переменных, и они истинны на одном и том же множестве означиваний этих переменных (то есть они задают одну и ту же булеву функцию). Булева формула минимальна, если не существует эквивалентной ей более короткой булевой формулы. Пусть MIN-FORMULA — совокупность минимальных булевых формул. Покажите, что если $\mathrm{P}=\mathrm{NP}$, то MIN-FORMULA $\in \mathrm{P}$.

Иерархия разностей $\mathrm{D}_{i} \mathrm{P}$ определяется рекурсивно так:

• Пусть MAX-CLIQUE $=\left\{ \langle G, k\rangle \mid \text{ наибольшая клика в }G\text{ имеет размер ровно }k\right\}$. Используя результат задачи 7.47, покажите, что MAX-CLIQUE DP-полна.

• Пусть $f: \mathcal{N} \longrightarrow \mathcal{N}$ — произвольная функция, для которой $f(n)=o(n \log n)$. Покажите, что TIME$(f(n))$ содержит только регулярные языки.

• Назовём регулярное выражение бесзвёздным, если оно не содержит операций звезды. Пусть $E Q_{\text{SF-REX }}=\left\{ \langle R, S\rangle \mid R\text{ и }S\text{ — эквивалентные бесзвёздные регулярные выражения}\right\}$. Покажите, что $E Q_{\text{SF-REX }}$ принадлежит coNP. Почему ваше рассуждение не работает для произвольных регулярных выражений?

• В этой задаче исследуется резолюция — метод доказательства невыполнимости кнф-формул. Пусть $\phi =C_{1} \wedge C_{2} \wedge \cdots \wedge C_{m}$ — формула в КНФ, где $C_{i}$ — её дизъюнкты. Пусть $\mathcal{C}=\left\{ C_{i} \mid C_{i} \text{ — дизъюнкт } \phi \right\}$. На шаге резолюции мы берём два дизъюнкта $C_{a}$ и $C_{b}$ из $\mathcal{C}$, в которых некоторая переменная $x$ входит положительно в один из дизъюнктов и отрицательно в другой. Таким образом, $C_{a}=\left(x \vee y_{1} \vee y_{2} \vee \cdots \vee y_{k}\right)$ и $C_{b}=\left(\bar{x} \vee z_{1} \vee z_{2} \vee \cdots \vee z_{l}\right)$, где $y_{i}$ и $z_{i}$ — литералы. Составим новый дизъюнкт $\left(y_{1} \vee y_{2} \vee \cdots \vee y_{k} \vee z_{1} \vee z_{2} \vee \cdots \vee z_{l}\right)$ и уберём повторяющиеся литералы. Добавим этот новый дизъюнкт в $\mathcal{C}$. Повторяем шаги резолюции, пока нельзя получить дополнительные дизъюнкты. Если пустой дизъюнкт ( ) входит в $\mathcal{C}$, объявим $\phi$ невыполнимой. Будем говорить, что резолюция корректна, если она никогда не объявляет выполнимые формулы невыполнимыми. Будем говорить, что резолюция полна, если все невыполнимые формулы объявляются невыполнимыми.

• Покажите, что P замкнут относительно гомоморфизма тогда и только тогда, когда $\mathrm{P}=\mathrm{NP}$.

• Пусть $A \subseteq 1^{*}$ — произвольный унарный язык. Покажите, что если $A$ NP-полна, то $\mathrm{P}=\mathrm{NP}$. (Подсказка: рассмотрите сведение $f$ за полиномиальное время от SAT к $A$. Для формулы $\phi$ пусть $\phi_{0100}$ — сведённая формула, в которой переменные $x_{1}, x_{2}, x_{3}$ и $x_{4}$ формулы $\phi$ приняли значения $0,1,0$ и 0 соответственно. Что произойдёт, если применить $f$ ко всем этим экспоненциально многим сведённым формулам?)

В ориентированном графе полустепенью захода вершины называется число входящих в неё рёбер, а полустепенью исхода — число выходящих из неё рёбер. Покажите, что следующая задача NP-полна. Дан неориентированный граф $G$ и выделенное подмножество $C$ его вершин; можно ли превратить $G$ в ориентированный граф, назначив направления всем его рёбрам так, чтобы у каждой вершины из $C$ полустепень захода или полустепень исхода была равна 0, а у каждой другой вершины $G$ полустепень захода была не менее 1?