ПОКРЫТИЕ МАТРИЦЫ (NP-полная задача)

Помогите с заданием по Математической логике и теории алгоритмов.

УСЛОВИЕ: Заданы матрица А = (аij) размером n x n с неотрицательными целыми элементами и целое число K.

ВОПРОС: Существует ли такое отображение f: {1,2, …, n} {-1, +1}, что a(ij)f(i)f(j) = K (сумма 1<=i,j<=n)

Доказать NP-полноту и принадлежность к классу NP

Источник: К этой задаче сводится МАКСИМАЛЬНЫЙ РАЗРЕЗ.

Комментарий: Задача NP-полна в сильном смысле и остается таковой даже в том случае, если требовать положительной оп¬ределенности матрицы А.