Задача о трехмерном сочетании

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

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

Верно ли, что заданное множество M\subseteq W\times X\times Y, где W,\,X и \,Y — непересекающиеся множества, равной мощности \,q, т.е. \mid W \mid = \mid X \mid = \mid Y \mid = q, содержит трехмерное сочетание, т.е. такое подмножество M'\subseteq M, что \mid M'\mid =q и никакие два разных элемента из M^\prime не имеют ни одной равной координаты?

См. также

Литература

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