577
правок
Изменения
Нет описания правки
{{Теорема
|statement=Всегда существует оптимально расписание такое, что в нем <tex>C_i \leqslant m + i Задача о проверке на пустоту пересечения двух КС- 1</tex> для любого <tex>i = 1 \ldots n</tex>, где <tex>m</tex> {{---}} количество станковграмматик неразрешима.|proof=Рассмотрим оптимальное расписание Пусть <tex>S^*</tex>A = \{ (G_1, в котором для любого <tex>i = 1 G_2) \ldots k - 1</tex> выполняется <tex>C_i mid L(G_1) \leqslant m + i - 1</tex>, но <tex>C_k > m + k - 1</tex>, где <tex>k</tex> максимально. Для начала покажем, что <tex>k</tex> не меньше <tex>2</tex>. Пусть есть оптимальное расписание, у которого <tex>C_1 > m</tex>. Это значит, что есть период времени <tex>t</tex> такой, что первая работа выполняется в момент <tex>t</tex> и не выполняется в <tex>t - 1</tex>. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент <tex>t - 1</tex>, будут выполняться на тех же станках, но в момент <tex>t</tex>, и наоборот. Значение <tex>C_i</tex> для каждой работы <tex>i</tex> не увеличится, так как <tex>C_1</tex> было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени <tex>t</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство <tex>C_1 cap L(G_2) = m</tex>.<br>Теперь пусть <tex>C_k = m + k + t</tex>, где <tex>t \geqslant 0varnothing \}</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множестваСведем [[Примеры неразрешимых задач:* множество <tex>A</tex> будет содержать все итерации обработки работ проблема соответствий Поста|проблему соответствий Поста]] к <tex>i = 1 \ldots k - 1</tex>* множество <tex>B</tex> overline{{---}} все итерации, запланированные в расписании <tex>S^*</tex> строго после момента времени <tex>k + m + t</tex>* множество <tex>C</tex> {{---}A} итерации обработки работ <tex>i = k + 1 \ldots n</tex>, которые в <tex>S^*</tex> запланированы на время <tex>k + m + t</tex> и раньшеТаким таким образомпоказав, мы имеем три непересекающихся множества, которые вместе с работой <tex>k</tex> покрывают все итерации всех работ.<br>Построим новое расписание <tex>S^*</tex>. Для начала расставим все работы из множества <tex>A \cup B</tex> так же, как они были запланированы в расписании <tex>S^*</tex>что дополнение проблемы неразрешимо. Так как <tex>C_i \leqslant m + i рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико- 1</tex> для <tex>i = 1 \ldots k - 1</tex>, ни одна итерация обработки в множестве <tex>B</tex> не поставлена раньше момента времени <tex>k + m + t</tex> множественных и к моменту времени <tex>C_k = m + k + t</tex> выполнено <tex>k</tex> работалгебраических операций|замкнуты относительно дополнения]], то это значит, что между моментами времени <tex>0</tex> и <tex>k + m - 1</tex> на каждой машине есть <tex>m</tex> различных простоев, то есть моментов, когда на ней ничего не обрабатывается. Значит, мы всегда сможем поставить на эти простои итерации обработки работы <tex>k</tex>, даже если эти простои пересекаются. Таким образом, <tex>C_k \leqslant m + k - 1</tex>из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.}}
Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики:* <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) =\{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>w^R</tex> {{---}} разворот <tex>w</tex>.* <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> для всех <tex>i =1, 2, \dots n</tex>. Тогда <tex>L(G_2) = Псевдокод ===\{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}</tex>.
Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>, и наоборот, если он не имеет решения, то <tex>L(G_2)</tex> не содержит строк такого вида, соответственно <tex>L(G_1) \cap L(G_2) === Асимптотика ===\varnothing</tex>.