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

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.