Изменения
Нет описания правки
# Рассмотрим языки $L_1 = \{\langle \Gamma, A, B\rangle|\Gamma$ - КС-грамматика, $A$ и $B$ - нетерминалы, множество слов, которые можно вывести из $A$ и $B$ совпадают$\}$, $L_2 = \{\langle \Gamma_1, \Gamma_2\rangle|\Gamma_1$ и $\Gamma_2$ - КС-грамматики, языки которых совпадают$\}$. Докажите, что $L_1\le L_2$ и $L_2 \le L_1$. Что можно сказать об $NP$-полноте языков $L_1$ и $L_2$ на основании этого?
# Сережа дал такое определение $NP$-полноты: язык $L$ является $NP$-полным по Серёже, если $L \in P \Rightarrow P = NP$. Прокомментируйте определение Серёжи.
# В этой и следующих заданиях вы можете считать известной $NP$-полноту следующих языков: $3SAT = $\{\varphi\,|\,$ существует набор $x$, где $\varphi(x)=1$, причем $\varphi$ находится в 3КНФ $\}$, $IND $= \{\langle G, k\rangle\,|\,$ в $G$ существует независимое множество размера $k\}$, $HAM = $\{G\,|\,$ в ориентированном графе $G$ существует гамильтонов цикл $\}$, а также всех, $NP$-полнота которых доказана в предыдущих заданиях. Докажите, что задача о клике $NP$-полна.
# Докажите, что задача о вершинном покрытии $NP$-полна.
# Изоморфизм подграфа $NP$-полный. Докажите $NP$-полноту следующего языка. Множество пар $\{\langle G_1, G_2 \rangle | G_1$ содержит $G_2$ как подграф $\}$.
