Банк задач по математике

Пример 7.20

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

?

Примечание.

?

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

Наидлиннейший путь (LP): Даны граф $G$ и целое $k>0$ , определить, есть ли в $G$ простой путь из не менее чем $k$ рёбер. (Путь простой, если ни одна вершина не встречается дважды.)

Пример 7.21

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

?

Примечание.

?

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

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

Пример 7.22

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

?

Пример 7.23

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

?

Примечание.

?

Выполнимость (SAT): Дана булева формула $F$ , определить, выполнима ли $F$ .

$\mathrm{CNF-SAT}$ : дана КНФ $F$ ; определить, выполнима ли $F$ .

Пример 7.24

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

?

Примечание.

?

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

Целочисленное программирование (IP): Даны целочисленная матрица $A$ размера $n \times m$ и $n$ -мерный целочисленный вектор $b$ , определить, существует ли $m$ -мерный целочисленный вектор $x$ такой, что $A x \geq b$ .

Пример 7.25

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

?

Примечание.

?

Трёхмерное паросочетание (3DM): Даны три попарно непересекающихся множества $A, B$ и $C$ , каждое из $n$ элементов, и множество $W \subseteq A \times B \times C$ , определить, есть ли у $W$ подмножество $W^{\prime }$ ровно из $n$ троек такое, что каждый элемент из $A \cup B \cup C$ встречается в $n$ тройках $W^{\prime }$ ровно один раз.

Выполнимость (SAT): Дана булева формула $F$ , определить, выполнима ли $F$ .

Пример 7.26

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

?

Примечание.

?

$\mathrm{3SAT}$ : дана 3-КНФ $F$ ; определить, выполнима ли $F$ .

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

Пример 7.27

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

?

Примечание.

?

$\mathrm{3SAT}$ : дана 3-КНФ $F$ ; определить, выполнима ли $F$ .

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

Задача 7.2.1

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

?

Задача 7.2.2

В этом упражнении мы рассматриваем альтернативное доказательство для примера 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 }$ .

?

Задача 7.2.3

(a)(b)(c)(d)

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

?

(a)

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

(b)

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

(c)

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

(d)

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

Примечание.

?

$\mathrm{3SAT}$ : дана 3-КНФ $F$ ; определить, выполнима ли $F$ .

Трёхмерное паросочетание (3DM): Даны три попарно непересекающихся множества $A, B$ и $C$ , каждое из $n$ элементов, и множество $W \subseteq A \times B \times C$ , определить, есть ли у $W$ подмножество $W^{\prime }$ ровно из $n$ троек такое, что каждый элемент из $A \cup B \cup C$ встречается в $n$ тройках $W^{\prime }$ ровно один раз.

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

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

Задача о поражении множества (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$ .

Задача 7.2.4

Рассмотрим следующие варианты проблемы $3\mathrm{SAT}$ :

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

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

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

?

Задача 7.2.5

Рассмотрим следующие проблемы: Изоморфизм подграфов (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$ .

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

?

Полиномиальная сводимость