Задача, которую вы формулируете, — классическая Exact 3‑Cover (X3C):
дано конечное множество U и коллекция троек S ⊆ (U choose 3). Вопрос: существует ли подмножество S' ⊆ S такое, что каждая точка u ∈ U принадлежит ровно одной троеке из S'? (обычно |U| = 3q и требуется S' размера q).

Покажем, что X3C — NP‑полная задача. Стандартная и простая редукция делает это из известной NP‑полной задачи 3‑Dimensional Matching (3DM).

1) Формулировки

3DM: даны три попарно непересекающихся множества X, Y, Z одинакового размера q и набор троек T ⊆ X × Y × Z. Вопрос: существует ли M ⊆ T размера q, т.е. множество троек, которое покрывает каждую вершину из X∪Y∪Z ровно один раз?X3C: как выше, дано U и набор троек S ⊆ (U choose 3), нужно выбрать S' покрывающее U ровно по одному разу.

2) X3C ∈ NP
Сертификат: подмножество троек S'. Проверка: (i) проверить, что |S'| = |U|/3 (или просто что каждая точка покрыта ровно один раз); (ii) для каждой точки u ∈ U подсчитать в скольких троек из S' она содержится — все счётчики должны быть равны 1. Это можно сделать за полиномиальное время.

3) Редукция 3DM → X3C
Вход: экземпляр 3DM = (X, Y, Z, T), где |X| = |Y| = |Z| = q и T ⊆ X×Y×Z.
Построение X3C‑входа (U, S):

Установим U := X ∪ Y ∪ Z (множества непересекающиеся, поэтому |U| = 3q).Пусть S := T (каждая тройка уже содержит по одному элементу из X, Y и Z, значит это тройки в U).

Это преобразование очевидно полиномиально (то же T, объединение множеств).

4) Корректность редукции

Если в 3DM есть совершенное соответствие M ⊆ T размера q (каждый элемент X∪Y∪Z встречается ровно в одной тройке M), то то же подмножество M даёт точное 3‑покрытие U в экземпляре X3C.Обратно, если в построенном экземпляре X3C есть S' ⊆ S, покрывающее каждую точку U ровно один раз, то так как S ⊆ X×Y×Z, каждая тройка из S' содержит по одному элементу из X, Y, Z; раз S' покрывает U ровно по одному разу, |S'| = q и S' является совершенным соответствием для исходного 3DM. То есть решение X3C даёт решение 3DM.

Следовательно 3DM имеет решение тогда и только тогда, когда соответствующий X3C‑экземпляр имеет решение. Поскольку 3DM — NP‑полная, X3C — NP‑трудная. В сочетании с тем, что X3C ∈ NP, получаем NP‑полноту X3C.

5) Примеры входов и соответствующие ответы

Пример 1 (YES):

3DM: X = {x1,x2}, Y = {y1,y2}, Z = {z1,z2} (q=2).
T = { (x1,y1,z1), (x1,y2,z2), (x2,y1,z1), (x2,y2,z2) }.
Здесь можно выбрать M = { (x1,y1,z1), (x2,y2,z2) } — покрываются все 6 элементов ровно по одному разу.Соответствующий X3C: U = X∪Y∪Z, S = T. Решение S' = M даёт точное 3‑покрытие — ответ YES.

Пример 2 (NO):

3DM: X = {x1,x2}, Y = {y1,y2}, Z = {z1,z2}.
T = { (x1,y1,z1), (x1,y2,z2), (x2,y1,z2) }.
Здесь |T|=3, но невозможно выбрать 2 тройки, покрывающие все 6 элементов без повторов (любая пара троек будет повторять какой‑то элемент).В X3C это даёт U = X∪Y∪Z, S = T, и очевидно X3C‑экземпляр — NO.

6) Замечания

Эта редукция очень прямая: 3DM и X3C по сути формально совпадают (X3C — точный ковёр троек по произвольному множеству размера 3q; 3DM — тот же вопрос, но тройки дополнительно структурированы по трём частям). Поэтому многие книги дают именно эту редукцию как «почти тождественную».Альтернативно можно редуцировать из 3‑SAT с более сложными наборами гаджетов (переменные, клаузы, вспомогательные элементы), но редукция из 3DM проще и короче.

Если нужно, могу показать полную редукцию из 3‑SAT в X3C с построением гаджетов (переменная/клауза/синхронизация) и привести пример на конкретной формуле 3‑CNF.