Доказательство NP-полноты проблемы

Question

Нам дан набор A = {a ₁ , a ₂ , ..., a _n }

Данные подмножестваА по имени В ₁ , В ₂ , ..., В _м .Если подмножество A с именем H имеет пересечение со всеми данными B, мы называем H «Покрывающим подмножеством».Существует ли какое-либо «подмножество покрытия» размера K (мощность H равна K) для данных A и Bs?Докажите, что эта проблема NP-Complete.

Мы должны свести некоторую известную проблему к проблеме «покрытия подмножества».

Answer 1

обновление Это называется ударным набором . Вы можете прочитать тот же ответ в статье Википедии.

Эта проблема, в некотором роде, двойна по отношению к заданной проблеме покрытия .

Мы изменим некоторую терминологию. Пусть {B1, B2, ...} будет элементами, а {a1, a2, ...} будет множествами. 'Set' ai содержит 'element' Bj в новой задаче, если set Bj содержит ai в исходной задаче.

Теперь вам просто нужно выбрать минимальное количество «наборов» ai, охватывающих все «элементы» Bj. И эта проблема является NP-полной, как показано в ссылке выше.

Чтобы прояснить преобразование, одно определение проблемы можно получить из другого, просто заменив набор / элемент и содержащий / содержащийся. Сравнить следующие

Каждый набор Bj содержит некоторый выбранный элемент ai
Каждый «элемент» Bj содержится в некотором выбранном «наборе» ai