Изменения
Нет описания правки
# Завершите доказательство, что $PRIMES \in NP$, доказав, суммарный размер рекурсивных сертификатов простоты простых делителей $n-1$ и время на их проверку является полиномом от длины $n$.
# Задача останова $HALT = \{\langle m, x \rangle | m$ - машина Тьюринга, $m(x) = 1\}$. Докажите, что $HALT$ является $NP$-трудной. Является ли она $NP$-полной?
# Изоморфизм подграфа $NP$-полный. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G_1, G_2 \rangle | G_1$ содержит $G_2$ как подграф $\}$.
# Задача реберного покрытия обратных связей $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ - ориентированный граф, который содержит подмножество из $k$ ребер, такое, что любой цикл $G$ содержит хотя бы одно из выбранных ребер $\}$.
# Задача целочисленного линейного программирования $NP$-полна. Докажите $NP$-полноту следующего языка. Множество систем линейных ограничений, которые имеют целочисленное решение.
# Задача поиска доминирующего множества $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ либо выбрана, либо имеет выбранного соседа $\}$.
# Задача пожарных депо. Докажите $NP$-полноту следующего языка. Множество троек $\{\langle G, k, d \rangle | G$ содержит множество из $k$ вершин, таких, что любая вершина $G$ имеет выбранную вершину на расстоянии не больше $d\}$.
# Задача о половинной клике. Докажите $NP$-полноту следующего языка. Множество графов $\{G | G$ имеет клику, содержащую ровно половину вершин $G\}$.
# Задача о раскраске $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G, k\rangle | G$ имеет правильную раскраску в $k$ цветов $\}$.
# Задача о раскраске в три цвета $NP$-полна. Докажите $NP$-полноту следующего языка. Множество графов $\{ G | G$ имеет правильную раскраску в три цвета $\}$. Что можно сказать про раскраску в два цвета?
# Докажите, что задача о гамильтоновом цикле в неориентированном графе $NP$-полна.
# Докажите, что задача о гамильтоновом пути в ориентированном графе $NP$-полна.
# Докажите, что задача о гамильтоновом пути в неориентированном графе $NP$-полна.
# Задача коммивояжера $NP$-полна. Докажите $NP$-полноту следующего языка. Множество пар $\{ \langle G, k\rangle | G$ --- взвешенный ориентированный граф, который содержит гамильтонов цикл весом не больше $k \}$.
# Задача о рюкзаке $NP$-полна. Докажите $NP$-полноту следующего языка. Даны предметы с весом $w_i$ и стоимостью $v_i$. Язык наборов $\{ \langle s, [(v_1, w_1), (v_2, w_2), \ldots (v_n, w_n)], k\rangle | $ можно выбрать предметы с суммарным весом не более $s$ и суммарной стоимостью не менее $k \}$.
