Трехмерное сочетание

Задача коммивояжера.

Гамильтонов цикл.

Разбиение.

Дано множество положительных целых чисел .

Можно ли разбить его на 2 подмножества так, чтобы суммы чисел в обоих подмножествах были равны?

Даны 3 множества А, В, С. Мощности их равны m, но их множества не пересекаются. Рассмотрим множество троек . Трехмерным сочетанием называется подмножество , в котором никакие две разные тройки не имеют ни одной равной координаты.

Кроме класса NP-полных проблем рассматривают еще класс NP- трудных проблем.

Проблема Т называется NP-трудной, если она удовлетворяет условию: Если то R сводится к Т за полиномиальное время.

Это условие совпадает со 2-м условием для NP-полных проблем. Следовательно, NP- полная проблема – это NP- трудная, принадлежащая классу NP.

В отличие от класса NPC, в котором находятся много известных и практически важных задач, в промежуточном классе NPI известно значительно меньше таких задач. Одна из них – задача «Изоморфизма 2-х графов».

Дата добавления: 2014-01-07