Это особый случай проблемы упаковки с максимальным набором, и обе проблемы A и B являются NP-Complete . Обратите внимание, что проблема является просто проблемой соответствия, еслиn=2 и это также легко, если n=1, Так что я придуn≥3,
Вместо того, чтобы задавать вопрос,
Здесь M непересекающиеся множества среди P наборы?
Давайте зададим следующий вопрос
Какое максимальное количество непересекающихся множеств мы можем получить из P наборы?
Ясно, что если второй вопрос отвечает за полиномиальное время, то и первый так же, так как все, что нам нужно сделать, это сравнить это максимальное значение с Mи выведите YES, еслиMменьше или равно этому максимуму и НЕТ в противном случае.
Кроме того, если первый вопрос отвечает за полиномиальное время, то второй тоже слишком, поскольку мы можем использовать бинарный поиск на M и получить ответ на второй вопрос и добавить только фактор O(logM)
Таким образом, мы можем сделать вывод, что оба вопроса эквивалентны. т. е. вопрос 1 разрешается в полиномиальное время тогда и только тогда, когда вопрос 2 тоже.
Также ясно, что проблемы в NP, так как мы можем легко проверить, что M Множества излагаемые являются непересекающимися.
Таким образом, вопрос теперь состоит в том, как мы сводим к этому известную проблему NP-Hard? Для этого мы избавляемся от задачи максимального набора упаковки . Я просто сконцентрируюсь на проблеме А, поскольку проблему В легко показать трудной, установивk=n−1
Рассмотрим произвольный случай задачи упаковки максимального множества T, Обратите внимание, что единственная разница между задачей A и исходной проблемой упаковки максимальных наборов состоит в том, что в задаче A размер наборов должен быть одинаковым. Позволятьt быть максимальным количеством элементов среди всех наборов в T, Если каждый набор вT иметь одинаковую мощность, мы закончили, и проблема покрытия множества - это точно проблема A. Теперь предположим, что для некоторого множества Si∈T, у нас есть |Si|<t, Мы просто добавляем(t−|Si|) элементы к Si которые не являются элементами любого набора в T, Мы повторяем этот процесс, пока все наборыSi∈Tимеют одинаковый размер. Понятно, что добавление новых элементов таким способом не меняет размер максимального числа непересекающихся множеств.
Итак, если мы можем решить проблему A за полиномиальное время мы можем решить проблему упаковки максимального набора за полиномиальное время, так как все, что нам нужно сделать, это удалить дополнительные элементы, которые мы добавили, и это не изменит размер максимального числа непересекающихся множеств в T,
РЕДАКТИРОВАТЬ - Некоторые Дополнительная информация о проблеме B
Предположим, что задача B имеет решение за полиномиальное время, теперь рассмотрим произвольный случай T проблемы А с nэлементов в наборе. Теперь мы добавляем фиктивный элементd к каждому набору в T, Теперь мы задаем следующий вопрос.
Какое максимальное количество непересекающихся множеств мы можем получить, взяв
n элементы из каждого набора?
Теперь мы знаем, что среди наборов в максимуме не более одного из них может содержать фиктивный элемент, поэтому, если ответ, который мы получаем как максимум, равен M, то фактическое максимальное количество наборов в экземпляре T (наша первоначальная проблема А) либо M или (M−1), но это дает постоянный коэффициент приближения для максимальной упаковки набора. И такое приближение возможно только еслиP=NP, Так что проблема Б тоже сложная.