NP

Предположим, что существует полиномиальная функция $p$ такая, что из $x \# y \in B$ следует $\left|y\right| \leq p(\left|x\right|)$. Покажите, что если $B \in \mathrm{NP}$, то prefix$(B) \in \mathrm{NP}$.

Покажите, что если $A=\left\{ x \mid (\exists u)[\left|u\right| \leq p(\left|x\right|), x \# u \in B\right\}$ для некоторой полиномиальной функции $p$ и если prefix$(B) \in P$, то $A \in P$.

Предположим, что $f$ — биекция. Покажите, что если $A \in \mathrm{NP}$, то $f(A) \in \mathrm{NP}$ и $f^{-1}(A) \in \mathrm{NP}$.

Покажите, что если $P=\mathrm{NP}$, то следующие функции полиномиально-временно вычислимы:

где $\leq_{\text{lex }}$ — лексикографический порядок на $\left\{ 0,1\right\}^{*}$.

Шесть мужчин, $\mathrm{A}, \mathrm{B}, \mathrm{C}, \mathrm{D}, \mathrm{E}$ и F, — единственные члены, имеющие право занять должности президента, вице-президента и секретаря в клубе NP. Известны следующие предпочтения этих мужчин:

• A не станет должностным лицом, если только E не президент.

• B не будет служить, если он превосходит по рангу C.

• B ни при каких условиях не будет служить вместе с F.

• C не будет служить одновременно с E и F.

• C не будет служить, если F президент или B секретарь.

• D не будет служить с C или E, если только он не превосходит их по рангу.

• E не станет вице-президентом.

• E не станет секретарём, если D — должностное лицо.

• E не будет служить с A, если только F тоже не служит.

• F не будет служить, если только он сам или C не президент.

Как можно распределить три должности, удовлетворив всем указанным условиям?

Полиция арестовала четверых мужчин по подозрению в убийстве. На допросе они сделали следующие заявления:

Джон: «Это сделал Ник». Ник: «Это сделал Билл». Дэн: «Я этого не делал». Билл: «Ник солгал, когда сказал, что это сделал я».

Если известно, что ровно один из них — настоящий убийца и ровно одно из вышеуказанных заявлений истинно, кто убийца?

Браун, Джонс и Смит работают в деревне NP пожарным, полицейским и учителем, хотя и не обязательно соответственно. Кто-то в деревне сообщил, что:

• Браун и учитель — соседи.

• Джонс и учитель — соседи.

• И Браун, и Смит — соседи пожарного.

• И полицейский, и пожарный — соседи Джонса.

• Все эти люди — соседи друг другу.

Однако на самом деле верны только два из этих утверждений. Можете ли вы определить, какую должность занимает каждый из мужчин?

И у Смитов, и у Тейлоров есть по два маленьких сына младше одиннадцати лет. Имена мальчиков, чей возраст, округлённый до ближайшего года, у всех разный, — Артур, Берт, Карл и Дэвид. Если брать возраст мальчиков только с точностью до ближайшего года, верны следующие утверждения:

• Артур на три года младше своего брата.

• Берт самый старший.

• Карл вдвое младше одного из мальчиков Тейлоров.

• Дэвид на пять лет старше младшего из мальчиков Смитов.

• Суммарный возраст мальчиков в каждой семье сегодня отличается на ту же величину, что и пять лет назад.

Сколько лет каждому мальчику и к какой семье он принадлежит?»

Постройте булевы формулы $F_{n, k}$, использующие операции $\wedge , \vee , \neg$ и переменные $x_{1}, x_{2}, \ldots , x_{n}$, такие что они вычисляют функцию $T_{n, k}$.

Покажите, что существуют булевы формулы $G_{n, k}$, использующие операции $\wedge , \vee$, $\neg$, переменные $x_{1}, x_{2}, \ldots , x_{n}$ и некоторые вспомогательные переменные $y_{1}, \ldots , y_{m}$, такие что (i) длина $G_{n, k}$ ограничена $n^{c}$ для некоторой константы $c>0$, и (ii) присваивание $t$ удовлетворяет $G_{n, k}$ тогда и только тогда, когда $t$ присваивает значение 1 хотя бы $k$ переменным из $\left\{ x_{1}, \ldots , x_{n}\right\}$.

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

Задача коммивояжёра (TSP): Дан полный граф $G=(V, E)$ с функцией стоимости $c: E \rightarrow \mathbf{N}$ и целое $k$, определить, существует ли тур (то есть гамильтонов цикл) графа $G$ с суммарной стоимостью рёбер, не превышающей $k$.

Изоморфизм графов (GIso): Даны два графа $G$ и $H$, определить, изоморфен ли $G$ графу $H$. (Два графа $G=\left(V_{1}, E_{1}\right)$ и $H=\left(V_{2}, E_{2}\right)$ изоморфны, если $\left|V_{1}\right|=\left|V_{2}\right|$ и существует взаимно однозначное отображение "на" $f: V_{1} \rightarrow V_{2}$ такое, что $\left\{ u, v\right\} \in E_{1}$ тогда и только тогда, когда $\left\{ f(u), f(v)\right\} \in E_{2}$. Функция $f$ называется изоморфизмом.)

Ограниченная PCP: Дано конечное множество упорядоченных пар $\left(x_{1}, y_{1}\right), \ldots$, $\left(x_{n}, y_{n}\right)$ строк над алфавитом $\Sigma$ и целое $K$ (в унарной форме $1^{K}$), определить, существует ли конечная последовательность целых чисел $\left(i_{1}, i_{2}, \ldots , i_{m}\right)$, с каждым $i_{j} \in \left\{ 1, \ldots , n\right\}$ и $m \leq K$, такая что

Ограниченное мощение (Bounded Tiling): Дано конечное число типов $t_{0}, t_{1}, \ldots , t_{n}$ цветных плиток и целое $K$ (в унарной форме $1^{K}$), определить, возможно ли замостить квадрат $K \times K$ цветными плитками этих типов, начиная с плитки типа $t_{0}$ в левом нижнем углу. (См. Упражнение 6 из Раздела 5.6 для подробностей определения.)

Покажите, что если $B$ — квадратная подматрица $A$, то $\left|\operatorname {det}(B)\right| \leq (\alpha q)^{q}$, где $\operatorname {det}(B)$ обозначает определитель матрицы $B$.

Покажите, что если $\operatorname {rank}(A)=r<m$, то существует ненулевой вектор $z$ такой, что $A z=0$ и максимальная абсолютная величина чисел в $z$ ограничена $(\alpha q)^{q}$.

Предположим, что $A x \geq b$ имеет целочисленное решение $x$. Пусть $a_{i}$ обозначает $i$-ю строку $A$, $b_{i}$ — $i$-ю компоненту $b$, а $e_{j}$ — $j$-й $m$-мерный единичный вектор (то есть все компоненты $e_{j}$ равны 0, кроме $j$-й компоненты, равной 1). Пусть $x$ — решение $A x \geq b$, максимизирующее число элементов следующего множества:

Докажите, что ранг $\mathcal{A}_{x}$ равен $m$.

Используя (c) выше, докажите Лемму 7.14.