Ответ - да, проблема все еще NP-Complete. для каждого набора Sя создайте поддельные элементы е'я, е''я и создайте новые наборы S'я= Sя∪ { е'я} и S''я= Sя∪ { е''я} . Легко проверить, что любой ударный набор старой системы является ударным набором новой системы. Кроме того, за исключением поддельных элементов, каждый элемент теперь поражает как минимум три набора.
Далее, для каждой пары наборов в новой системе (давайте назовем их Tя и TJ чтобы избежать путаницы), создайте поддельный элемент Икся ж и добавьте его к Tя и TJ . Ясно, что в полученной системе множеств все пары попарно пересекаются, но исходный оптимальный набор попаданий все еще остается оптимальным набором попаданий для этой новейшей системы.
Без каких-либо дополнительных ограничений проблема выглядит так же сложно, как и оригинальная.
Кстати, доказательство того, что действительно оптимальное решение не использовало бы никаких поддельных элементов, не тривиально. Во-первых, мы можем предположить, что заданный ударный набор для новой системы не включает в себя е'я или е''я , поскольку в противном случае мы можем переместить элементы в исходные элементы наборов и получить ударный набор аналогичного размера. Несколько сложнее понять, почему элементы Икся ж не находятся в оптимальном наборе ударов. Поскольку это утомительно, я бы просто оставил подсказку: создайте граф, соединяющий два набора Sя и SJ в исходной системе, если Икся ж соединяет два набора, которые являются производными от этих наборов. Утверждают, что этот граф в минимальном множестве попаданий должен быть 3регулярный, и, таким образом, число ребер в нем строго превышает число множеств, представленных в виде вершин. Таким образом, можно найти меньший ударный набор для этих наборов.