О некоторых свойствах образов трансформированных задач

Одним из способов доказательства NP-полноты задачи является полиномиальное сведение (трансформация) к ней задачи, NP-полнота которой уже установлена. При этом изучению свойств полученного образа, на наш взгляд, уделяется недостаточно внимания. В 1985 г. в работе Дж. Лагариаса и А. М. Одлыжко предложен метод решения NP-полной задачи о рюкзаке, дающий верное решение для “практически всех” рюкзаков, плотность которых не превышает $0,6463\dots$ В настоящей работе рассматривается вопрос о том, в какую область задач о рюкзаке (относительно плотности рюкзаков) при доказательстве NP-полноты попадают образы следующих задач: $3$-ВЫП, Раскрашиваемость, Точное покрытие.