Доказать NP – полноту предложенной задачи

[Kosat]

Задание кафедры

1.Доказать принадлежность классу $NP$ предложенной задачи
2. Решить одну из двух проблем:
а. доказать NP–полноту предложенной задачи
б. построить приближенный алгоритм решения предложенной задачи и показать его точность.

Задача ( вариант):

1. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ
УСЛОВИЕ. Заданы множество элементов данных $A$, размер $s(a) \in Z+$ каждого элемента данных $a \in A$, время поступления $r(a) \in Z_0+$ и время $d(a) \in Z+$ окончания работы с элементом данных $a \in A$, положительное целое число $D$ – размер области памяти.
ВОПРОС. Существует ли для множества элементов данных $A$ допустимое распределение памяти? Иначе говоря, существует ли такая функция $\sigma: A \rightarrow \left\{1, 2, ..., D\right\}$, что для каждого элемента $a \in A$ интервал
$I(a)=[\sigma(a), \sigma(a) + s(a) - 1]$
содержится в $[1, D]$, причем для любых $a, a' \in A$, если множество $I(a) \cap I(a')$ не пусто, то либо $d(a) \leq r(a')$, либо $d(a') \leq r(a)$?

Решение
1. Легко видеть, что предложенная задача принадлежит классу $NP$, так как недетерминированному алгоритму нужно лишь предположить подмножество $\sigma'$ из множества всех распределений $\sigma$ и проверить за полиномиальное время что для каждого элемента $a \in A$ интервал
$I(a)=[\sigma' (a), \sigma' (a) + s(a) - 1]$
содержится в $[1, D]$, причем для любых $a, a' \in A$, если множество $I(a) \cap I(a')$ не пусто, то либо $d(a) \leq r(a')$, либо $d(a') \leq r(a)$.
То есть:
1. Для каждой пары $a, a' \in A$ проверить:
$r(a) \geq r(a')$.
2. Если предыдущее условие выполняется, проверить:
$r(a) \leq d(a')$.
3. Далее проверим $I(a) \cap I(a')$ с помощью отношения частичного порядка. Если предыдущее условие выполняется, проверить:
$\sigma(a) \geq \sigma(a')$.
4. Если предыдущее условие выполняется, проверить:
$\sigma(a) \leq \sigma(a') + s(a') - 1$.
5. Если предыдущее условие выполняется, то данное распределение – неправильное. Если не выполняется – то правильное.
$|A|\cdot(|A|-1)\cdot(|A|-1)\cdot(|A|-1)\cdot(|A|-1)$ – полином пятой степени, задача принадлежит к классу $NP$.
2. Мы сводим к этой задаче задачу 3-РАЗБИЕНИЯ. Пусть состоящее из $3m$ элементов множество $C$; положительная целая граница $B$; положительный целый размер $s(x)$ удовлетворяющий $B/4 < s(x)< B/2$ для каждого элемента $x$ из $C$; и сумма размеров $C$ равная точно $mB$ – произвольный экземпляр 3-РАЗБИЕНИЯ. Тогда $C$ разделяется на непересекающиеся множества $C_1,...,C_m$ такие, что каждое $C_i$ содержит точно $3$ элемента из $C$, размер каждого $C_i$ точно равен $B$. Обозначим элементы этих множеств как:
$C_1={c_1_1, c_1_2, c_1_3}$
$C_2={c_2_1, c_2_2, c_2_3}$
$C_3={c_3_1, c_3_2, c_3_3}$
…
$C_m={c_m_, c_m_2, c_m_3}$
Переформулируем исходную задачу как поиск заполнения «плитками» «пола». Сформируем множество из всех доступных комбинаций $r(a), d(a), \sigma(a), \sigma(a) + s(a) - 1$. Далее сгруппируем координаты всех точек по трое так, чтобы они удовлетворяли нашим условиям и не пересекались одна с другой. Таким образом, мы свели к этой задаче задачу 3-РАЗБИЕНИЯ

----------

Первая часть не доведена до конца (как минимум, нужно показать для всех остальных углов "маленьких прямоугольников", а не только для нижних правых; также не мешало бы использовать определение, то есть с помощью машины Тьюринга), вторая - полностью неправильна. В учебнике сказано, что задача сводится к задаче 3-РАЗБИЕНИЯ - но как, не ясно.
Есть несколько примеров сданных заданий других вариантов, но они не помогают.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Kosat
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[patzer2097]

Ну принадлежность классу $\operatorname{NP}$ более или менее очевидна, и Ваше доказательство вроде бы нормальное с точностью до опечаток. А опечаток, кстати, хватает - например, в условие, вероятно, Вы хотели добавить "либо $a=a'$" после

Kosat в сообщении #950845 писал(а):

для любых $a, a' \in A$, если множество $I(a) \cap I(a')$ не пусто, то либо $d(a) \leq r(a')$, либо $d(a') \leq r(a)$

Что касается NP-полноты, я пока не понимаю даже того, как Вы строите сведение. Но это куда более сложная часть задачи.

[Kosat]

Спасибо за указание опечатки, но именно так было в условии (хотя я понимаю её разумность; интересно также узнать о других). Я старался переписывать аккуратно. У меня есть сканы книги, откуда это всё.

Что касается второй части, то я написал что-то просто "от фонаря". Лишь бы было. Но не прокатило. Я ПРАВДА не понимаю, как свести нашу задачу к 3-РАЗБИЕНИЮ (в книге сказано, что так надо решать).

P.S. Опечатку в $c_m_1$ заметил.

[patzer2097]

Kosat в сообщении #950993 писал(а):

Спасибо за указание опечатки, но именно так было в условии (хотя я понимаю её разумность; интересно также узнать о других).

нужно "функцию $\sigma$" вместо "подмножество $\sigma$" в первой строке решения; в пункте 3 непонятно, что значит

Kosat в сообщении #950845 писал(а):

<...>проверим $I(a) \cap I(a')$ с помощью<...>

в пунктах 3 и 4 Вы проверяете только $\sigma(a)\in I(a')$ вместо $I(a)\cap I(a')=\varnothing$; я мог еще что-то упустить.

(3-РАЗБИЕНИЕ)

А кстати, как определяется 3-РАЗБИЕНИЕ, может я смогу тут чем-то помочь?

[Kosat]

Спасибо за указания помарок - первая особенно к месту. Что касается второй, то "первая часть не доведена до конца (как минимум, нужно показать для всех остальных углов "маленьких прямоугольников", а не только для нижних правых)".

Вот учебник с задачей:
http://rutracker.org/forum/viewtopic.php?t=3509871

Мне помогают эти статьи:
http://cgi.csc.liv.ac.uk/~ped/teachadmi ... ed_np.html
http://www.di.unipi.it/~luccio/GJ%20Cap%203.PDF

В них про 3-РАЗБИЕНИЕ.
Name: 3-Partition [SP15] 3
Input: A set $A$ of $3m$ elements; a positive integer bound $B$; for each element $x$ in $A$ a positive integer size $s(x)$ that satisfies $B/4< s(x)< B/2$, and is such that the sum of the sizes of elements in $A$ is exactly $mB$.
Question: Can $A$ be partitioned into $m$ disjoint sets $A_1,...,A_m$ such that each $A_i$ contains exactly $3$ elements of $A$ and each $A_i$ has total size equal to $B$?

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Kosat
Наберите все формулы и термы $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
См. также тему Что такое карантин, и что нужно делать, чтобы там оказаться.
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»