Задача о точном покрытии 3-множествами: различия между версиями

'''Задача о точном покрытии 3-множествами'''(''3-Set exact cover problem'') -

одна из основных ''<math>\cal NP</math>-полных'' задач.

Верно ли, что заданное семейство <math>C</math>

трехэлементных

подмножеств заданного конечного множества <math>X</math>

такого, что <math>\mid X\mid =3q</math> для некоторого натурального <math>q</math>,

содержит ''точное покрытие'' множества <math>X</math>, т.е. такое подсемейство

См. также ''Задача о вершинном покрытии, Задача о выполнимости, Задача о клике, Задача о неэквивалентности регулярных выражений, Задача о разбиении, Задача о трехмерном очетании, Классы <math>\cal P</math> и <math>\cal NP</math>, Метод локальной замены, Метод построения компонент, Метод сужения задачи, Полиномиальная сводимость трансформируемость), <math>\cal NP</math>-полная задача, Труднорешаемая задача.''

[Ахо-Хопкрофт-Ульман],

[Касьянов/95]