Изменения
Нет описания правки
# Задача о раскраске в три цвета $NP$-полна. Докажите $NP$-полноту следующего языка. Множество графов $3COL=\{ G | G$ имеет правильную раскраску в три цвета $\}$. Что можно сказать про раскраску в два цвета?
# Задача о рюкзаке $NP$-полна. Докажите $NP$-полноту следующего языка. Даны предметы с весом $w_i$ и стоимостью $v_i$. Язык наборов $KNAPSACK=\{ \langle s, [(v_1, w_1), (v_2, w_2), \ldots (v_n, w_n)], k\rangle | $ можно выбрать предметы с суммарным весом не более $s$ и суммарной стоимостью не менее $k \}$.
# Задача целочисленного линейного программирования $NP$-полнатрудна. Докажите $NP$-полноту трудность следующего языка. Множество систем линейных ограничений, которые имеют целочисленное решение.
# Сережа дал такое определение $NP$-полноты: язык $L$ является $NP$-полным по Серёже, если $L \in P \Rightarrow P = NP$. Прокомментируйте определение Серёжи.
# Юра дал такое определение класса $NP$: это задачи, который можно решить перебором. Прокомментируйте определение Юры.
