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

Пример 7.36

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

?

Пример 7.37

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

?

Пример 7.38

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

?

Пример 7.39

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

?

Пример 7.40

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

?

Пример 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

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

?

Задача 7.4.1

Для каждой из следующих задач определите, является ли она $\mathrm{NP}$ -полной или принадлежит $P$ . Если она $\mathrm{NP}$ -полна, найдите сведение от известной $\mathrm{NP}$ -полной задачи к ней. Если она принадлежит $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)

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

(j)

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

Задача 7.4.2

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

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

?

(a)

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

(b)

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

(c)

Planar Connected-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$ .

Задача 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-3Sat, является 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-3Sat, является NP-полной: Дана 3-КНФ формула $F$ с планарным неполярным представлением; определить, выполнима ли $F$ .

Задача 7.4.5

(a)(b)(c)

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

?

(a)

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

(b)

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

(c)

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

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