Уменьшить следующую проблему до SAT

21

Здесь проблема. Даны , где каждый T i{ 1 , , n } . Существует ли подмножество S { 1 , , n } с размером не более k таким, что S T i для всех i ? Я пытаюсь свести эту проблему к SAT. Моя идея решения будет иметь переменную х яk,n,T1,,TmTi{1,,n}S{1,,n}kSTiixi для каждого из 1 в . Для каждого T i создайте предложение ( x i 1nTi , если Т я = { я 1 , ... , я K } . Тогда и все эти пункты вместе. Но это явно не полное решение, так как оно не представляет ограничение, которое S должен иметь не более k элементов. Я знаю, что я должен создать больше переменных, но я просто не уверен, как. Итак, у меня есть два вопроса:(xi1xik)Ti={i1,,ik}Sk

  1. Моя идея решения на правильном пути?
  2. Как создать новые переменные, чтобы их можно было использовать для представления ограничения мощности ?k
Аден Донг
источник
5
Просто замечание: Ваша проблема известна как HITTING SET , которая является эквивалентной формулировкой проблемы SET COVER .
А.Шульц

Ответы:

13

Похоже, вы пытаетесь вычислить трансверсаль гиперграфа размера . То есть { T 1 , , T m } - ваш гиперграф, а Sk{T1,,Tm}S - ваш трансверсал. Стандартный перевод состоит в том, чтобы выразить предложения, как у вас, а затем перевести ограничение длины в ограничение количества элементов.

Поэтому используйте существующую кодировку, т. а затем добавьте предложения, кодирующие 1 i n x ik .1jmiTjxi1inxik

- ограничение мощности. Существуют различные переводы ограничений кардинальности в SAT.1inxik

Самый простой, но довольно большой перевод ограничения мощности - это просто . Таким образом, каждая дизъюнкция представляет ограничение ¬ i X x i - для всех подмножеств X в { 1 , , n }X{1,,n},|X|=k+1iX¬xi¬iXxiX{1,,n}размером к + 1. Таким образом, мы гарантируем, что нет возможности установить более k переменных. Обратите внимание, что это не полиномиальный размер в k

Некоторые ссылки на статьи о более компактных переводах ограничений кардинальности, которые имеют полиномиальный размер в k :

Если вы действительно заинтересованы в решении таких проблем, возможно, лучше сформулировать их как псевдобулевы (см. Вики-статью о псевдобулевых задачах ) и использовать псевдобулевы решатели (см. Псевдобулевы соревнования ). Таким образом, ограничения мощности являются просто псевдобулевыми ограничениями и являются частью языка - надеюсь, псевдобулев решатель будет обрабатывать их напрямую и, следовательно, более эффективно.

MGwynne
источник
1
Пожалуйста, опишите все ссылки в ближайшее время (по крайней мере, автора и название), чтобы люди могли найти документы, если ссылки не работают. Вероятно, лучше использовать DOI, если доступно.
Рафаэль
1
@ Рафаэль Хороший вопрос! Извините, я должен был сделать это для начала. Я сейчас обновил все ссылки; Я не уверен, что Springer предоставит DOI, но сейчас должно быть достаточно информации, чтобы найти их, если ссылки разорвутся. Примечание: я не делаю ссылки на официальные PDF-файлы Springer, чтобы избежать проблем с доступом.
MGwynne
Но похоже, что сокращение, которое вы дали, не за полиномиальное время, верно?
Аден Донг
@AdenDong Вы ничего не сказали о полиноме;). Простое кардинальное ограничение перевод я Упоминание не многочлен (но при фиксированном к ). Переводы ограничения мощности, приведенные в перечисленных мною работах , полиномиальны по k - с использованием новых переменных. Я обновил свой ответ, чтобы сделать это более понятным. kkk
MGwynne
MGwynne, я всегда связываю официальный DOI, даже если он платный, чтобы быть ориентированным на будущее, и бесплатные версии дополнительно. Но сейчас любой может найти документы, так что все в порядке.
Рафаэль
6

k

Γ2,1+Γ2,1+

Я предполагаю, что вы ищете явное сокращение, но если нет, вы всегда можете просто вернуться к теореме Кука-Левина .

Люк Мэтисон
источник