Задача о точном покрытии 3-множествами

Материал из WikiGrapp
Перейти к:навигация, поиск

Задача о точном покрытии 3-множествами(3-Set exact cover problem) — одна из основных \mathcal NP-полных задач. Формулируется следующим образом.

Верно ли, что заданное семейство C трехэлементных подмножеств заданного конечного множества X такого, что \mid X\mid =3q для некоторого натурального q, содержит точное покрытие множества X, т.е. такое подсемейство C'\subseteq C, что каждый элемент из X содержится ровно в одном элементе из C?

См. также

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.
  • Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.