NP-полнота

SAT принадлежит NP.

Сформулируйте следующую головоломку в виде булевой формулы $F$ и решите её, определив, выполнима ли $F$:

За пять игр до конца регулярного сезона командный математик доложил менеджеру бейсбольной команды A: «Мы всё ещё можем попасть в плей-офф, если победим команду $B$, а также если команда $B$ побеждает команду $C$, то команда $C$ побеждает команду $D$, а если мы проигрываем команде $C$, то команда $D$ также побеждает либо команду $B$, либо команду $C$». Позже, среди оставшихся пяти игр, каждая команда выиграла хотя бы одну игру, но ни одна команда не выиграла все свои оставшиеся игры, и не было ни одной ничьей. Был ли у команды A шанс попасть в плей-офф? Если да, то как?

Сформулируйте следующую головоломку в виде булевой формулы $F$ и решите её, определив, выполнима ли $F$:

Трое мужчин по имени Льюис, Миллер и Нельсон занимают должности бухгалтера, кассира и управляющего в ведущем универмаге города NP. Об их работе известно следующее:

• Если Нельсон — кассир, то Миллер — управляющий.

• Если Нельсон — управляющий, то Миллер — бухгалтер.

• Если Миллер — не кассир, то Льюис — управляющий.

• Если Льюис — бухгалтер, то Нельсон — управляющий.

Какую должность занимает каждый из мужчин?

Гамильтонов цикл (HC): Дан граф $G$, определить, есть ли в $G$ гамильтонов цикл.

HC принадлежит NP.

(Обход коня) Найти обход шахматной доски $8 \times 8$ конём, который посещает каждую клетку ровно один раз и возвращается на начальную клетку.

Вершинное покрытие (VC): Даны граф $G$ и положительное целое $k$, определить, есть ли в $G$ вершинное покрытие размера не более $k$.

VC принадлежит NP.

Задача о поражении множества (HS): Даны подмножества $A_{1}, A_{2}, \ldots , A_{n}$ множества $S$ и целое $k$, определить, существует ли подмножество $A \subseteq S$ размера $\left|A\right| \leq k$ такое, что $A \cap A_{i} \neq \emptyset$ для всех $i=1, \ldots , n$.

HS принадлежит NP.

Сформулируйте следующую логическую головоломку как экземпляр задачи HS и решите её, найдя правильное подмножество.

Три женщины, Джоан, Мишель и Трейси, сделали следующие заявления о своём возрасте.

Джоан: «Мне 92 года. Я на два года младше Мишель. Я на один год старше Трейси». Мишель: «Я не самая младшая. Мы с Трейси отличаемся по возрасту на три года. Трейси 25 лет». Трейси: «Я моложе Джоан. Джоан 23 года. Мишель на три года старше Джоан». Известно, что из трёх заявлений каждого человека ровно два верны. Каков их возраст?

IS принадлежит NP.

(Задача о восьми ферзях) Расставить восемь ферзей на доске $8 \times 8$ так, чтобы они не били друг друга. (В шахматах ферзь бьёт другую фигуру, если они находятся в одной строке, или в одном столбце, или на одной диагонали.)

3DM принадлежит $\mathrm{NP}$.

IP принадлежит $\mathrm{NP}$.

Сформулируйте следующую логическую головоломку как экземпляр задачи IP и решите её, решив соответствующую систему неравенств.

Профессор $X$ выступал с коллоквиумом на кафедре теории сложности. Начав доклад, он заметил, что 15 присутствующих в аудитории удовлетворяют следующим условиям:

• Студентов было больше, чем профессоров.

• Профессоров-мужчин было больше, чем студентов-мужчин.

• Студентов-мужчин было больше, чем студенток.

• Была хотя бы одна женщина-профессор.

Пять минут спустя в комнату вбежал ещё один человек. Однако появление этого человека не изменило вышеуказанные четыре условия. Этот человек — мужчина или женщина, студент или профессор?

Prime принадлежит NP.

Докажите, что 683 — простое число.

Для любого множества $A$ пусть $A^{\prime }=\left\{ w \# 0^{n} \mid w\text{ — суффикс некоторого }x\text{ из }A\text{ с }\left|x\right|=n\right\}$, а $A^{\prime \prime }=\left\{ w \mid w\text{ имеет суффикс }x\text{ из }A\right\}$. Покажите, что если $A$ принадлежит NP, то $A^{\prime }$ и $A^{\prime \prime }$ также принадлежат $\mathrm{NP}$.

Для любого множества $B \subseteq \left\{ 0,1\right\}^{*} \# \left\{ 0,1\right\}^{*}$ пусть $\operatorname {prefix}(B)=\left\{ x \# u \mid x, u \in \left\{ 0,1\right\}^{*},\left(\exists v \in \left\{ 0,1\right\}^{*}\right) x \# u v \in B \right\}$.

Функция $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ называется полиномиально-временно вычислимой, если существует полиномиально-временная ДМТ, вычисляющая функцию $f$ (то есть на входе $x$ она останавливается за $p(|x|)$ шагов для некоторого полинома $p$, со строкой $f(x)$ на выходной ленте). Функция $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ называется полиномиально честной, если существует полиномиальная функция $p$ такая, что $|f(x)| \leq p(|x|)$ и $|x| \leq p(|f(x)|)$ для всех $x \in \left\{ 0,1\right\}^{*}$. Предположим, что $f$ полиномиально-временно вычислима и полиномиально честна.

Сформулируйте следующие головоломки как экземпляры задач из NP, а затем решите головоломки, найдя свидетелей для этих экземпляров:

Пороговая функция $T_{n, k}$ — это булева функция, определённая следующим образом:

Докажите, что следующие числа простые: $293,587,65537,214177$.

Покажите, что следующие задачи принадлежат NP:

Пусть $A$ — целочисленная матрица размера $n \times n$, а $b$ — $n$-мерный целочисленный вектор. Пусть $\alpha$ — максимальная абсолютная величина чисел в $A$ и $b$, а $q= \max \left\{ m, n\right\}$.

HC $\leq_{m}^{P} \mathrm{LP}$.

$\mathrm{VC} \equiv_{m}^{P}$ IS.

GIso $\equiv_{m}^{P}$ DGIso.

SAT $\leq_{m}^{P}$ CNF-SAT.

$\mathrm{VC} \leq_{m}^{P} \mathrm{IP}$.

$3\mathrm{DM} \leq_{m}^{P} \mathrm{SAT}$.

$3\mathrm{SAT} \leq_{m}^{P} \mathrm{VC}$.

$3\mathrm{SAT} \leq_{m}^{p} \mathrm{HC}$.

Докажите, что CNF-Sat $\leq_{m}^{P}$ 3Sat.

В этом упражнении мы рассматриваем альтернативное доказательство для примера 7.25. Заменим условия (1) и (2) условием (3): для каждого $a \in A \cup B \cup C$ существует тройка $w \in W^{\prime }$ такая, что (i) $a \in w$, и (ii) если $w^{\prime } \in W^{\prime }, w^{\prime } \neq w$, то $a \notin w^{\prime }$. Переведите это условие в булеву формулу $G$ над переменными $x_{w}$ и покажите, что $G$ выполнима тогда и только тогда, когда $W$ имеет трёхмерное паросочетание $W^{\prime }$.

Постройте следующие сведения:

Рассмотрим следующие варианты проблемы 3Sat:

3Sat-Exactly-One: дана 3-КНФ $F$; определить, существует ли присваивание $t$ переменным $F$, которое присваивает значение TRUE ровно одному литералу в каждом дизъюнкте $F$.

3Sat-Not-All: дана 3-КНФ $F$; определить, существует ли присваивание $t$ переменным $F$, которое присваивает значение TRUE одному или двум литералам (но не всем трём) в каждом дизъюнкте $F$.

Покажите, что 3Sat, 3Sat-Exact-One и 3Sat-Not-All полиномиально эквивалентны относительно $\leq_{m}^{P}$.

Рассмотрим следующие проблемы: Изоморфизм подграфов (SGIso): даны два графа $G_{1}= \left(V_{1}, E_{1}\right)$ и $G_{2}=\left(V_{2}, E_{2}\right)$; определить, существует ли инъективное отображение $f: V_{1} \rightarrow V_{2}$ такое, что для всех $u, v \in V_{1}$, $\left\{ u, v\right\} \in E_{1}$ влечёт $\left\{ f(u), f(v)\right\} \in E_{2}$.

Автоморфизм графа (GAuto): дан граф $G= (V, E)$; определить, существует ли инъективная функция $f: V \rightarrow V$, отличная от тождественной функции, такая, что для всех $u, v \in V,\left\{ u, v\right\} \in E$ тогда и только тогда, когда $\left\{ f(u), f(v)\right\} \in E$.

Докажите все полиномиальные сведения, какие вы сможете найти, среди трёх проблем GIso, SGIso и GAuto.

Покажите, что если $P=\mathrm{NP}$, то все непустые собственные подмножества $A$ множества $\Sigma^{*}$ являются NP-полными.

Если известно, что $A$ является $\mathrm{NP}$-полным, будет ли $A^{2}$ всегда $\mathrm{NP}$-полным?

В доказательстве теоремы Кука мы использовали условия (4.1) $-(4.5)$ на ???-образных окнах над матрицей $S$, чтобы обеспечить выполнение условия (4). Покажите, что если вместо этого работать с ???-образными окнами над матрицей $S$, то никакие условия на эти окна не могут обеспечить выполнение условия (4). Другими словами, покажите, что следующее соотношение не выполняется ни для какого подмножества $T \subseteq \left(\Gamma^{\prime }\right)^{4}$ :

где $\alpha_{i}$ обозначает $i$-ю конфигурацию, соответствующую присваиваниям переменным $y_{i, j, a}$.

Покажите, что в доказательстве теоремы Кука функция $f_{1}$ необходима. То есть никакое определение подмножества $T$ не может сделать истинным следующее: $F_{x}^{\prime }=f_{0} f_{2} f_{3} f_{4}$ выполнима тогда и только тогда, когда $x \in L(M)$.

В доказательстве теоремы Кука можно убрать условие (1), если заменить условие (4') новым условием (4'') над шестиклеточными окнами ???-образной формы. Найдите подусловия над шестиклеточными, ???-образными окнами, которые делают $\left(4^{\prime \prime }\right)$ эквивалентным условию (4) без предположения о выполнении условия (1).

Булева формула, являющаяся произведением литералов, называется элементарным произведением. ДНФ (дизъюнктивная нормальная форма) — это сумма элементарных произведений.

Предположим, что $A$ и $B$ — два $\mathrm{NP}$-полных множества. Покажите, что $A \cup B$ и $A \cap B$ не обязательно являются $\mathrm{NP}$-полными, если $P \neq \mathrm{NP}$. Всегда ли $A \cup B$ является $\mathrm{NP}$-полным, если $A \cap B=\emptyset$?

Это упражнение использует обозначения, определённые в упражнении 3 раздела 7.1.

Предположим, что $P \neq \mathrm{NP}$. Пусть $A$ и $B$ — два множества, полных для $c o-\mathrm{NP}$ (т.е. $\bar{A}$ и $\bar{B}$ являются NP-полными). Обязательно ли $A B$ принадлежит co-NP? Обязательно ли $A B$ является co-NP-полным? Возможно ли, что $A B$ принадлежит $P$? Обоснуйте свой ответ.

Предположим, что в доказательстве теоремы Кука мы убираем условие (1) и заменяем условие $\left(4^{\prime }\right)$ на $(\overline{4})$, которое задаёт некоторые подусловия на пятиклеточных окнах одной из четырёх форм, показанных на рисунке 7.11. Покажите, что никакие такие подусловия на пятиклеточных окнах не могут сделать (4) эквивалентным $\left(4^{\prime }\right)$.

Рассмотрим альтернативное доказательство теоремы Кука, приведённое в примере 7.33. Пусть $T \subseteq \left(\Gamma^{\prime }\right)^{6}$ — множество, соответствующее двенадцати окнам рисунка 7.10; то есть $(a, b, c, d, e, g) \in T$ тогда и только тогда, когда $(a, b, c, d, e, g)$ имеет один из двенадцати видов на рисунке 7.10 и удовлетворяет соответствующим условиям, заданным в трёх случаях. Покажите, что если существует отображение $\phi :\left(\Gamma^{\prime }\right)^{3} \rightarrow \left(\Gamma^{\prime }\right)^{3}$, такое что $(a, b, c, d, e, g) \in T$ тогда и только тогда, когда $\phi (a, b, c)= (d, e, g)$, то $L(M)$ принадлежит $P$.

В этом упражнении мы рассматриваем иную схему для доказательства теоремы Кука. Вместо того чтобы присоединять символ состояния к ленточному символу, который в данный момент сканируется головкой ленты, мы можем определить отдельные булевы переменные для представления состояния и положения головки ленты. То есть, помимо переменных $y_{i, j, a}$ (только для $a \in \Gamma$), для каждого $i=0, \ldots , r(n)$ и каждого $q \in Q$ мы определяем переменную $Q_{i, q}$, означающую, что символ состояния конфигурации $\alpha_{i}$ равен $q$, а для каждой пары $(i, j)$, с $i, j \in \left\{ 0, \ldots , r(n)\right\}$, — переменную $H_{i, j}$, означающую, что в конфигурации $\alpha_{i}$ головка ленты сканирует $j$-й символ. Чтобы доказать теорему Кука в этой схеме, нам нужно определить шесть булевых функций $g_{1}, \ldots , g_{6}$, таких что для $k=1, \ldots , 6, g_{k}=1$ тогда и только тогда, когда выполняется приведённое ниже условие $(k)$:

(1) Для каждого $i=0, \ldots , r(n)$, $\alpha_{i}$ находится ровно в одном состоянии.

(2) Для каждого $i=0, \ldots , r(n)$, головка сканирует ровно одну ячейку в $\alpha_{i}$.

(3) Для каждого $i=0, \ldots , r(n)$ и каждого $j=0, \ldots , r(n)$, $j$-я ячейка $\alpha_{i}$ содержит ровно один символ.

(4) $\alpha_{0}$ — начальная конфигурация $M$ на входе $x$.

(5) $\alpha_{r(n)}$ — допускающая конфигурация.

(6) Для каждого $i=0, \ldots , r(n)-1$, $\alpha_{i} \vdash \alpha_{i+1}$.

Предположим, что $g_{1}, \ldots , g_{5}$ удовлетворяют условию, что $g_{k}=1$ тогда и только тогда, когда выполняется условие $(k)$. Также пусть $g_{6}$ равно

где $\Delta =-1$, если $D=L$, и $\Delta =1$, если $D=R$. Найдите контрпример, опровергающий, что $G_{x}=\prod_{i=1}^{6} g_{i}=1$ тогда и только тогда, когда $M$ допускает $x$. Найдите новую функцию $g_{6}$, для которой $G_{x}=1$ тогда и только тогда, когда $M$ допускает $x$.

Остаётся ли задача VC NP-полной, если каждое ребро должно покрываться ровно одной вершиной?

Докажите, что MCG является NP-полной.

Partition является NP-полной.

Knapsack является NP-полной.

BP является NP-полной.

Покажите, что следующая задача является NP-полной: Даны положительные целые числа $a_{1}, \ldots , a_{n}$; определить, выполняется ли

SMT является NP-полной.

Для каждой из следующих задач определите, является ли она $\mathrm{NP}$-полной или принадлежит $P$. Если она $\mathrm{NP}$-полна, найдите сведение от известной $\mathrm{NP}$-полной задачи к ней. Если она принадлежит $P$, найдите для неё полиномиальный алгоритм.

Докажите, что следующие варианты задачи VC являются $\mathrm{NP}$-полными:

Полярным представлением КНФ $F$ называется двудольный граф $G_{F}= \left(V_{1}, V_{2}, E\right)$, где $V_{1}$ — множество всех переменных, а $V_{2}$ — множество всех дизъюнктов в $F$, причём в $E$ есть ребро между $x_{i} \in V_{1}$ и $c_{j} \in V_{2}$ тогда и только тогда, когда переменная $x_{i}$ встречается в дизъюнкте $c_{j}$ (в виде $x_{i}$ или $\bar{x}_{i}$). Докажите следующие утверждения:

Неполярным представлением КНФ $F$ называется граф $G_{F}=(V, E)$, множество вершин $V$ которого состоит из всех литералов и всех дизъюнктов в $F$, а множество рёбер $E$ состоит из всех пар $\left\{ x, \bar{x}\right\}$ по всем переменным $x$ в $F$, а также всех пар литерал-дизъюнкт $\left\{ z, c\right\}$ таких, что $z$ встречается в $c$. Докажите следующие утверждения:

$(k, \ell )$-КНФ $F$ — это КНФ, в которой каждый дизъюнкт содержит ровно $k$ литералов, а каждая переменная встречается не более чем в $\ell$ дизъюнктах. Задача $(k, \ell )$-Sat — это задача 3SaT, ограниченная $(k, \ell )$-КНФ. Докажите следующие результаты:

Покажите, что Min-VC является NP-полной задачей поиска.

TSP является NP-полной.

Задача $r$-Approx-TSP является NP-полной для всех $r>1$.

Задача $r$-Approx-VC является NP-полной для некоторого $r>1$.

Для каждого $d \geq 3$ задача $r$-Approx-VC-$d$ является NP-полной для некоторого $r>1$.

Для $1<r<\sqrt{2}$ задача $r$-Approx-BST является NP-полной.

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

Для каждой из следующих задач оптимизации покажите, что она NP-полна:

Покажите, что для каждой из следующих задач оптимизации II существует коэффициент приближения $r>1$ такой, что $r$-Approx- $\Pi$ является $\mathrm{NP}$-полной.

Для графа $G$ его рёберно-квадратный граф $G^{2}$ — это граф, полученный из $G$ заменой каждого ребра $\left\{ u, v\right\}$ на копию $G$, называемую $G_{u, v}$, и соединением как $u$, так и $v$ с каждой вершиной в $G_{u, v}$.

Покажите, что для каждой из следующих задач оптимизации $\Pi$ существует константа $\varepsilon >0$ такая, что $n^{\varepsilon }$-Approx- $\Pi$ является $\mathrm{NP}$-полной.