Изменения

|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 G_2) \mid L(G_1) \cap L(G_2) = 1 \ldots k - 1varnothing \}</tex> выполняется . Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>C_i \leqslant m + i - 1overline{A}</tex>, но <tex>C_k > m + k таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико- 1</tex>множественных и алгебраических операций|замкнуты относительно дополнения]], где <tex>k</tex> максимальното из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.  Для начала покажем, что любого экземпляра ПСП <tex>k</tex> не меньше <tex>2</tex>(x_1, x_2, .. Пусть есть оптимальное расписание, у которого <tex>C_1 > m</tex>. Это значит, что есть период времени <tex>t</tex> такой, что первая работа выполняется в момент <tex>tx_n)</tex> и не выполняется в <tex>t - 1</tex>(y_1, y_2, .. Поменяем эти периоды времени местами. То есть все работы, которые выполнялись в момент <tex>t - 1y_n)</tex>, будут выполняться на тех же станках, но в момент над алфавитом <tex>t\Sigma</tex>, и наоборот. Значение можно подобрать символ <tex>C_i\# \notin \Sigma</tex> для каждой работы . Для каждого экземпляра построим грамматики:* <tex>iG_1 : S \rightarrow aSa \mid a\#a</tex> не увеличится, так как для всех <tex>C_1</tex> было минимальным из них, а значит ни одна работа не могла быть закончена раньше периода времени <tex>ta \in \Sigma</tex>. Будем продолжать этот процесс, пока не будет выполнено равенство Тогда <tex>C_1 L(G_1) = m\{ w\#w^R \mid w \in \Sigma^* \}</tex>.<br>Теперь пусть , где обозначение <tex>C_k = m + k + tw^R</tex>, где {{---}} разворот <tex>t \geqslant 0w</tex>. Будем называть ''итерацией обработки'' работы обработку на одной машине. Разобьем все работы на три множества:* множество <tex>AG_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> будет содержать все итерации обработки работ для всех <tex>i = 1 , 2, \ldots k - 1dots n</tex>* множество . Тогда <tex>B</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 \} все итерации, запланированные в расписании <tex>S^*m \geqslant 1 \}</tex> строго после момента времени . Если данный экземпляр ПСП имеет решение, то <tex>k + m + tL(G_2)</tex>* множество содержит хотя бы одну строку вида <tex>Cw\#w^R</tex> {{---}} итерации обработки работ , поэтому <tex>i = k + 1 L(G_1) \cap L(G_2) \ne \ldots nvarnothing</tex>, которые в и наоборот, если он не имеет решения, то <tex>S^*L(G_2)</tex> запланированы на время не содержит строк такого вида, соответственно <tex>k + m + tL(G_1) \cap L(G_2) = \varnothing</tex>. Таким образом, мы имеем три непересекающихся множества, которые вместе с работой свели проблему соответствий Поста к <tex>k\overline{A}</tex> покрывают все итерации всех работ, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.

== См. также ==Таким образом, мы имеем:{{Утверждение* [[O2Cmax|statement= Пусть дана грамматика <tex>O2 \mid \mid C_{max}G</tex>]]* [[Opi1sumu|, <tex>O \mid p_{ij} L(G) = 1 \mid \sum U_iL</tex>]]. Тогда следующие задачи неразрешимы:* [[Opij1di|# Содержит ли <tex> O \mid p_{i, j} = 1, d_i \mid - L</tex>]]тандемный повтор.* [[Opij1sumwu|# Содержит ли <tex> O \mid p_{i, j} = 1 \mid - \sum w_{i} U_{i}L</tex>]]== Источники информации ==палиндром.* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 171-174 ISBN 978-3-540-69515-8 [[Категория: Алгоритмы и структуры данных]][[Категория: Теория расписаний]]