Теорема Кука

Покажите, что если $P=\mathrm{NP}$, то все непустые собственные подмножества $A$ множества $\Sigma^{*}$ являются NP-полными.

Если известно, что $A$ является $\mathrm{NP}$-полным, будет ли $A^{2}$ всегда $\mathrm{NP}$-полным?

В доказательстве теоремы Кука мы использовали условия (4.1) $-(4.5)$ на ???-образных окнах над матрицей $S$, чтобы обеспечить выполнение условия (4). Покажите, что если вместо этого работать с ???-образными окнами над матрицей $S$, то никакие условия на эти окна не могут обеспечить выполнение условия (4). Другими словами, покажите, что следующее соотношение не выполняется ни для какого подмножества $T \subseteq \left(\Gamma^{\prime }\right)^{4}$ :

где $\alpha_{i}$ обозначает $i$-ю конфигурацию, соответствующую присваиваниям переменным $y_{i, j, a}$.

Покажите, что в доказательстве теоремы Кука функция $f_{1}$ необходима. То есть никакое определение подмножества $T$ не может сделать истинным следующее: $F_{x}^{\prime }=f_{0} f_{2} f_{3} f_{4}$ выполнима тогда и только тогда, когда $x \in L(M)$.

В доказательстве теоремы Кука можно убрать условие (1), если заменить условие (4') новым условием (4'') над шестиклеточными окнами ???-образной формы. Найдите подусловия над шестиклеточными, ???-образными окнами, которые делают $\left(4^{\prime \prime }\right)$ эквивалентным условию (4) без предположения о выполнении условия (1).

Булева формула, являющаяся произведением литералов, называется элементарным произведением. ДНФ (дизъюнктивная нормальная форма) — это сумма элементарных произведений.

Предположим, что $A$ и $B$ — два $\mathrm{NP}$-полных множества. Покажите, что $A \cup B$ и $A \cap B$ не обязательно являются $\mathrm{NP}$-полными, если $P \neq \mathrm{NP}$. Всегда ли $A \cup B$ является $\mathrm{NP}$-полным, если $A \cap B=\emptyset$?

Это упражнение использует обозначения, определённые в упражнении 3 раздела 7.1.

Предположим, что $P \neq \mathrm{NP}$. Пусть $A$ и $B$ — два множества, полных для $c o-\mathrm{NP}$ (т.е. $\bar{A}$ и $\bar{B}$ являются NP-полными). Обязательно ли $A B$ принадлежит co-NP? Обязательно ли $A B$ является co-NP-полным? Возможно ли, что $A B$ принадлежит $P$? Обоснуйте свой ответ.

Предположим, что в доказательстве теоремы Кука мы убираем условие (1) и заменяем условие $\left(4^{\prime }\right)$ на $(\overline{4})$, которое задаёт некоторые подусловия на пятиклеточных окнах одной из четырёх форм, показанных на рисунке 7.11. Покажите, что никакие такие подусловия на пятиклеточных окнах не могут сделать (4) эквивалентным $\left(4^{\prime }\right)$.

Рассмотрим альтернативное доказательство теоремы Кука, приведённое в примере 7.33. Пусть $T \subseteq \left(\Gamma^{\prime }\right)^{6}$ — множество, соответствующее двенадцати окнам рисунка 7.10; то есть $(a, b, c, d, e, g) \in T$ тогда и только тогда, когда $(a, b, c, d, e, g)$ имеет один из двенадцати видов на рисунке 7.10 и удовлетворяет соответствующим условиям, заданным в трёх случаях. Покажите, что если существует отображение $\phi :\left(\Gamma^{\prime }\right)^{3} \rightarrow \left(\Gamma^{\prime }\right)^{3}$, такое что $(a, b, c, d, e, g) \in T$ тогда и только тогда, когда $\phi (a, b, c)= (d, e, g)$, то $L(M)$ принадлежит $P$.

В этом упражнении мы рассматриваем иную схему для доказательства теоремы Кука. Вместо того чтобы присоединять символ состояния к ленточному символу, который в данный момент сканируется головкой ленты, мы можем определить отдельные булевы переменные для представления состояния и положения головки ленты. То есть, помимо переменных $y_{i, j, a}$ (только для $a \in \Gamma$), для каждого $i=0, \ldots , r(n)$ и каждого $q \in Q$ мы определяем переменную $Q_{i, q}$, означающую, что символ состояния конфигурации $\alpha_{i}$ равен $q$, а для каждой пары $(i, j)$, с $i, j \in \left\{ 0, \ldots , r(n)\right\}$, — переменную $H_{i, j}$, означающую, что в конфигурации $\alpha_{i}$ головка ленты сканирует $j$-й символ. Чтобы доказать теорему Кука в этой схеме, нам нужно определить шесть булевых функций $g_{1}, \ldots , g_{6}$, таких что для $k=1, \ldots , 6, g_{k}=1$ тогда и только тогда, когда выполняется приведённое ниже условие $(k)$:

(1) Для каждого $i=0, \ldots , r(n)$, $\alpha_{i}$ находится ровно в одном состоянии.

(2) Для каждого $i=0, \ldots , r(n)$, головка сканирует ровно одну ячейку в $\alpha_{i}$.

(3) Для каждого $i=0, \ldots , r(n)$ и каждого $j=0, \ldots , r(n)$, $j$-я ячейка $\alpha_{i}$ содержит ровно один символ.

(4) $\alpha_{0}$ — начальная конфигурация $M$ на входе $x$.

(5) $\alpha_{r(n)}$ — допускающая конфигурация.

(6) Для каждого $i=0, \ldots , r(n)-1$, $\alpha_{i} \vdash \alpha_{i+1}$.

Предположим, что $g_{1}, \ldots , g_{5}$ удовлетворяют условию, что $g_{k}=1$ тогда и только тогда, когда выполняется условие $(k)$. Также пусть $g_{6}$ равно

где $\Delta =-1$, если $D=L$, и $\Delta =1$, если $D=R$. Найдите контрпример, опровергающий, что $G_{x}=\prod_{i=1}^{6} g_{i}=1$ тогда и только тогда, когда $M$ допускает $x$. Найдите новую функцию $g_{6}$, для которой $G_{x}=1$ тогда и только тогда, когда $M$ допускает $x$.