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

Пример 7.36

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

?

Примечание.

?

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

Пример 7.37

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

?

Примечание.

?

Граф минимальной связности (MCG): Даны $n$ подмножеств $X_{1}, X_{2}, \ldots , X_{n}$ множества $X$ и положительное целое число $k$ ; найти граф $G$ на множестве вершин $X$ , содержащий не более $k$ рёбер, такой что каждый порождённый подграф $\left.G\right|_{X_{i}}$ графа $G$ , $1 \leq i \leq n$ , связен.

Пример 7.38

$\mathrm{Partition}$ является NP-полной.

?

Примечание.

?

Разбиение (Partition): Даны $n$ положительных целых чисел $a_{1}, a_{2}, \cdots , a_{n}$ ; определить, существует ли разбиение $\left(I_{1}, I_{2}\right)$ множества $\left\{ 1,2, \cdots , n\right\}$ такое, что $\sum_{i \in I_{1}} a_{i}=\sum_{i \in I_{2}} a_{i}$ .

Пример 7.39

$\mathrm{Knapsack}$ является NP-полной.

?

Примечание.

?

Рюкзак (Knapsack): Даны $2 n+2$ неотрицательных целых чисел $c_{1}, c_{2}, \ldots , c_{n}$ , $p_{1}, p_{2}, \ldots , p_{n}, s$ , и $k$ ; определить, существуют ли $x_{1}, x_{2}, \ldots , x_{n} \in \left\{ 0,1\right\}$ , удовлетворяющие $\sum_{i=1}^{n} c_{i} x_{i} \leq s$ и $\sum_{i=1}^{n} p_{i} x_{i} \geq k$ .

Пример 7.40

$\mathrm{BP}$ является NP-полной.

?

Примечание.

?

Упаковка в контейнеры (BP): Даны $n+2$ положительных целых чисел $a_{1}, a_{2}, \cdots , a_{n}$ , $c$ , и $k$ ; определить, можно ли разбить список $\left(a_{1}, a_{2}, \cdots , a_{n}\right)$ на $k$ подсписков так, чтобы сумма $a_{i}$ в каждом подсписке не превышала $c$ .

Пример 7.41

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

\int _{0}^{2 \pi }\left(\prod _{i=1}^{n} \cos \left(a_{i} t\right)\right) d t \neq 0

?

Пример 7.42

$\mathrm{SMT}$ является NP-полной.

?

Примечание.

?

Минимальное дерево Штейнера (SMT): Даны множество из $n$ целочисленных точек на евклидовой плоскости и положительное целое число $k$ ; определить, существует ли дерево Штейнера над терминальными точками $x_{1}, \ldots , x_{n}$ , суммарная длина рёбер которого не превышает $k$ .

Задача 7.4.1

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

?

(a)

Даны граф $G$ , две вершины $s$ и $t$ в $G$ и положительное целое число $k$ ; определить, существует ли между $s$ и $t$ путь длины не более $k$ .

(b)

Даны граф $G$ , две вершины $s$ и $t$ в $G$ и положительное целое число $k$ ; определить, существует ли между $s$ и $t$ путь длины не менее $k$ .

(c)

Дан ориентированный граф $G$ ; определить, содержит ли $G$ цикл нечётной длины.

(d)

Дан ориентированный граф $G$ ; определить, содержит ли $G$ цикл чётной длины.

(e)

Дан граф $G$ ; определить, содержит ли $G$ цикл нечётной длины.

(f)

Даны полный граф $G$ с весами на рёбрах, три подмножества вершин $X_{1}, X_{2}$ , $X_{3}$ и положительное целое число $k$ ; определить, существует ли подграф $H$ графа $G$ веса $\leq k$ , содержащий остовное дерево для каждого из $X_{1}, X_{2}$ и $X_{3}$ . (Остовным деревом для подмножества $X \subseteq V$ называется связный подграф $H$ графа $G$ на множестве вершин $X$ , не содержащий циклов.)

(g)

Даны граф $G=(V, E)$ и положительное целое число $k$ ; определить, существует ли подмножество $T \subseteq E$ из не более чем $k$ рёбер, такое что каждая вершина из $V$ инцидентна хотя бы одному ребру из $T$ .

(h)

Неэквивалентность регулярных выражений: Даны два регулярных выражения $r_{1}$ и $r_{2}$ без операции звезды Клини; определить, выполняется ли $L\left(r_{1}\right) \neq L\left(r_{2}\right)$ .

(i)

Ограниченная $\mathrm{PCP}$ (см. упражнение 7(d) раздела 7.1).

(j)

Ограниченное замощение (Bounded Tiling) (см. упражнение 7(e) раздела 7.1).

Задача 7.4.2

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

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

?

(a)

Planar VC: задача $\mathrm{VC}$ , ограниченная планарными графами. (Планарным графом называется граф, который можно нарисовать на двумерной плоскости так, что никакие два ребра не пересекаются в точке, не являющейся вершиной.)

(b)

Cubic VC: задача $\mathrm{VC}$ , ограниченная кубическими графами. (Кубическим графом называется граф, в котором каждая вершина имеет степень три.)

(c)

Planar Connected- $\mathrm{VC}$ -4: Даны планарный граф $G=(V, E)$ , в котором каждая вершина из $V$ имеет степень не более 4, и целое число $k>0$ ; определить, существует ли вершинное покрытие $C$ графа $G$ размера $k$ такое, что порождённый подграф $\left.G\right|_{C}$ на множестве вершин $C$ связен.

(d)

Дан граф $G$ ; определить, имеет ли $G$ вершинное покрытие $C$ , удовлетворяющее следующим условиям:

(i) Подграф $\left.G\right|_{C}$ , порождённый $C$ , не имеет изолированных точек.

(ii) Каждая вершина из $C$ смежна с вершиной, не принадлежащей $C$ .

Примечание.

?

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

Задача 7.4.3

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

Полярным представлением КНФ $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}$ ). Докажите следующие утверждения:

?

(a)

$(x+y+\bar{z})(\bar{x}+z+w)(\bar{x}+z+\bar{w})(\bar{y}+z+u)(\bar{y}+z+\bar{u})$ имеет планарное полярное представление и выполнима тогда и только тогда, когда $x+y=z$ .

(b)

Существует 3-КНФ формула $F$ с планарным полярным представлением и тремя переменными $x, y$ и $z$ , такая что $F$ выполнима тогда и только тогда, когда $x y=z$ .

(c)

Существует 3-КНФ формула $F$ с планарным полярным представлением и тремя переменными $x, y$ и $z$ , такая что $F$ выполнима тогда и только тогда, когда $x \oplus y=z$ . [Указание: $x \oplus y=x(\bar{x}+\bar{y})+(\bar{x}+\bar{y}) y$ .]

(d)

Следующая задача, называемая Planar Polar- $3\mathrm{SAT}$ , является NP-полной: Дана 3-КНФ формула $F$ с планарным полярным представлением; определить, выполнима ли $F$ . [Указание: примените к построению тот факт, что $x \oplus (x \oplus y)=y$ и $(x \oplus y) \oplus y=x$ .]

Задача 7.4.4

(a)(b)

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

?

(a)

Если неполярное представление КНФ-формулы $F$ планарно, то её полярное представление также обязательно планарно. Однако обратное не обязательно верно.

(b)

Следующая задача, называемая Planar Nonpolar- $3\mathrm{SAT}$ , является NP-полной: Дана 3-КНФ формула $F$ с планарным неполярным представлением; определить, выполнима ли $F$ .

Задача 7.4.5

(a)(b)(c)

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

?

(a)

При любом $k>0$ каждая $(k, k)$ -КНФ $F$ выполнима.

(b)

При любом $\ell >0$ задача (2, $\ell$ )- $\mathrm{SAT}$ полиномиально разрешима. (На самом деле задача 2Sat, являющаяся задачей $3\mathrm{SAT}$ , ограниченной КНФ с не более чем 2 литералами в каждом дизъюнкте, полиномиально разрешима.)

(c)

$(3,4)$ - $\mathrm{SAT}$ является $N P$ -полной.

Дополнительные NP-полные задачи