Сложна ли следующая проблема NP?

15

Рассмотрим набор множеств над базовым множеством где и , и пусть будет положительным целым числом.F = { F 1 , F 2 , , F n } U = { e 1 , e 2 , , e n } | F i | « П е яF я кF={F1,F2,,Fn}U={e1,e2,,en}|Fi| neiFik

Цель состоит в том, чтобы найти другой набор множеств над , чтобы каждый мог быть записан как объединение не более чем взаимно непересекающихся множеств. в а также мы хотимбыть минимальным (т. е. совокупное количество элементов во всех наборах должно быть как можно меньше).С = { С 1 , С 2 , ... , С т } U Р я K ( K < < | C | )C={C1,C2,,Cm}UFik (k<<|C|) C m 1 | C j | СCm1|Cj|C

Обратите внимание, что имеет такой же размер с , но размер является неопределенным.F U CFUC

Кто-нибудь может сказать, является ли вышеуказанная проблема NP-трудной? (установить покрытие? упаковка? идеальное покрытие)

Спасибо за ваше время.

Rhein
источник
Я не понимаю, в чем «проблема». Что вы хотите ответить?
Анкур
4
Почему эта проблема не тривиальна, если установить C = {U}?
Цуёси Ито
6
Помимо точного значения «намного меньше», у меня все еще есть проблемы с пониманием проблемы. Как указано в редакции 11, мне кажется, что оптимальным решением всегда является C = ∅ или C = {∅}. Если мы добавим ограничение, что C содержит хотя бы одно непустое множество в качестве элемента, то C = {{e}} для некоторого элемента e∈U будет оптимальным.
Цуёси Ито
1
Пожалуйста, внимательно прочитайте свой вопрос. Вы никогда не говорили, что C должен быть выбран так, чтобы F_i можно было записать как объединение множеств из C.
Tsuyoshi Ito
1
Могу ли я рассматривать проблему NORMAL SET BASIS как подзадачу оригинальной?
Рейн

Ответы:

2

Лемма. Проблема NP-сложная.

Эскиз доказательства. Мы игнорируем ограничения | F i | n = | U | в опубликованной задаче, поскольку для любого экземпляра задачи ( F , U , k ) экземпляр ( F = F n , U = U n , k ) получается путем объединения n независимых копий ( F , U , K ) (где я|Fi|n=|U|(F,U,k)(F=Fn,U=Un,k)n( F, U, к )яй экземпляр F использует я й копии U в качестве базового набора) эквивалентен, и удовлетворяет ограничение (оно имеет | F ' я | & le ; п « п 2 = | U ' | ).FяU| F'я| n n2= | U'|

Мы даем скидку от 3-сат. Для наглядности на первом этапе редукции мы игнорируем ограничения e iF i в опубликованной задаче. На втором этапе мы опишем, как удовлетворить эти ограничения при сохранении правильности сокращения.еяFя

Начальная ступень. Зафиксируйте любую формулу 3-SAT ϕ . Предположим, что в WLOG каждое предложение содержит ровно три литерала (каждый использует свою переменную). Создайте следующий экземпляр ( F , U , k ) опубликованной проблемы с k = 3 .φ( F, U, к )к = 3

Пусть n будет числом переменных в ϕ . Есть 3 п + 1 элементов в U : один элемент т (для «истина»), и для каждой переменной х I в ф , три элемента х I , ¯ х я и е I (для «ложь»).Nφ3 н + 1UTИксяφИксяИкс¯¯¯яея

Для каждого элемента в U существует множество синглтона , содержащее только этот элемент в F . Любое решение С , следовательно , включает в себя каждый из этих наборов, которые способствуют их общий размер 3 п + 1 к стоимости C .UFС3 н + 1С

Кроме того, для каждой переменной х I в ф существует множество «переменная» { х я , ¯ х я , F I , т } в F . Для каждого предложения в ϕ существует множество «предложений» в F, состоящее из литералов в предложении и t . Так , например, положение х 1¯ х 2х 3 дает множество { х 1 , ¯ х 2 , хИксяφ{ хя, х¯¯¯я, фя, т }FφFTИкс1 х¯¯¯2 х33 , т } в F .{х1, х¯¯¯2,х3, т }F

Утверждение 1. Сокращение корректно: ϕ выполнимо тогда и только тогда, когда какое-либо решение C имеет стоимость j | C j | = 5 н + 1 .φСΣJ|СJ| =5н+1

(только если) Пусть ϕ выполнимо. Построим решение C, состоящее из 3 n + 1 одноэлементных множеств, плюс для каждой переменной x i пара, состоящая из истинного литерала и t . (Например, { ¯ х я , т } , если х я ложно.) Стоимость C затем 5 п + 1 . φС3 н + 1ИксяT{ х¯¯¯я, т }ИксяС5 н + 1

Каждый набор переменной { х я , ¯ х я , F I , т } является объединением трех множеств: пара , состоящей из истинных буквальных и т , плюс два набора одноэлементных, по одному для каждого из двух других элементов. (Например, { ¯ х я , т } , { х я } , { е I } .){хя, х¯¯¯я,фя, т }T{ х¯¯¯я, т } , {хя} , { fя}

Каждый набор раздела (например , { х 1 , ¯ х 2 , х 3 , т } ) является объединением трех множеств: пара , состоящая из т и истинного буквальным, плюс два набора одноэлементных, по одному для каждого из двух других литералов. (Например, { х 1 , т } , { ¯ х 2 } , { х 3 } .){х1, х¯¯¯2,х3, т }T{х1, т } , { х¯¯¯2} , { x3}

(если) Предположим, что существует решение C размером 5 n + 1 . Решение должно содержать 3 n + 1 одноэлементных набора, а также другие наборы с общим размером 2 n .С5 н + 13 н + 12 н

Рассмотрим сначала п «переменной» наборов, каждый из вида { х я , ¯ х я , F I , т } . Множество является объединением непересекающихся не более трех множеств C . Без ограничения общности это несвязное объединение двух синглетонов и пары (в противном случае разбиение множеств в C достигает этого без увеличения стоимости). Обозначим пару P i . Пары P i и P j для разных переменных x i и x j различны, посколькуN{хя, х¯¯¯я,фя, т }ССпяпяпJИксяИксJР я содержу й я , ¯ х я , или е я , но Р J нет. Следовательно, сумма размеров этих пар равна 2 n . Таким образом, эти пары являются единственными не-одиночными множествами в решении. пяИксяИкс¯¯¯яеяпJ2 н

Далее рассмотрим «положения» устанавливает, например, { х я , ¯ х J , х к , т } . Каждый такой набор должен быть объединением не более трех наборов в C , то есть до двух одноэлементных наборов и по меньшей мере одной пары P i , P j или P k . При обследовании пар и множества п, оно должно быть объединение двух одноэлементных и одной пары, и эта пара должна иметь вид { х я , т } или { ¯ х J , т }{хя, х¯¯¯J,хК, т }СпяпJпК{хя, т }{ х¯¯¯J, т }(буквальное и т ).T

Следовательно, следующее назначение удовлетворяет ф : правопреемником истинные каждой переменной х я такое , что Р я = { х я , т } , правопреемником ложь каждой переменной х я такое , что Р я = { ¯ х я , т } , и назначить остальные переменные произвольно.φИксяпя= {хя, т }Иксяпя= { х¯¯¯я, т }

Этап 2. Произведенный выше экземпляр ( F , U , k = 3 ) не удовлетворяет ограничению e iF i, указанному в описании задачи. Исправьте этот недостаток следующим образом. Упорядочите множества F i и элементы e i в U так, чтобы каждый одноэлементный набор соответствовал своему элементу e i . Пусть m - количество предложений в ϕ , поэтому | F | = 1 + 4 n +(F,U, к = 3 )еяFяFяеяUеямφм и | U | = 1 + 3 н .|F|=1+4n+m|U|=1+3n

Пусть ( F , U , k = 4 ) обозначает случай, полученный следующим образом. Пусть быть множество 2 п + 2 м новых элементов искусственных, два для каждого не одноточечного множества в F . Пусть U ' = U A . Пусть F ' содержит наборы одноэлементные из F , плюс, для каждого не одноточечного множества F я в F , два множества F я{ в(F,U,k=4)A2n+2mFU=UAFFFiFi , a ' i } и { a i , a ' i } , где a i и a ' i являются двумя элементами в A, выбранными уникально для F i . Сейчас | F | = | U | = 1 + 5 n + 2 m и (при правильном упорядочении F и U ) ограничение eFi{ai,ai}{ai,ai}aяa'яAFя| F'| = | U'| =1+5н+2мF'U'IFi выполняется для каждого множестваFi .е'яF'яF'я

В заключение отметим, что ( F , U , k = 4 ) имеет решение стоимости | A | + 5 n + 1, если исходный экземпляр ( F , U , k = 3 ) имеет решение стоимостью 5 n + 1 .( F', U', к'= 4 )|A|+5n+1(F,U, к = 3 )5 н + 1

(если) Учитывая любое решение C стоимостью 5 n + 1 для ( F , U , k = 3 ) , добавление n + m устанавливает { a i , a i } (по одному для каждого не-одиночного F i , поэтому разбиение A ) на C дает решение ( F , U , k = 4 ) стоимостиС5n+1(F,U,k=3)n+m{ai,ai}| A | + c o s t ( C ) = | A | + 5 н + 1 .

(только если) Рассмотрим любое решение C для ( F , U , k = 4 ) стоимости | A | + 5 н + 1 . Рассмотрим любую пару без одноэлементные множества F я{ я , в " я } и { в I , ' я } в F ' . Каждый является несвязанным объединением не более 4 множеств в C . По аргументу local-exchange один из этих наборов является { a i , a i }, а остальные не содержат a i или a i - в противном случае это свойство может быть достигнуто путем локальной модификации наборов, без увеличения стоимости ... (недостаток деталей, вот почему я называю этоэскизом). Таким образом, удаление { a i , a i } множеств из C дает решение C для ( F , U ,k = 3 ) стоимостью 5 н + 1 .

Нил Янг
источник