О принадлежности классу MAX-SNP-трудных задач MIN-PC и MASC-GP$(n)$

Известно, что задача о минимальном покрытии конечного множества точек плоскости множеством прямых (MIN-PC) и задача о минимальном аффинном разделяющем комитете, сформулированная в пространстве фиксированной размерности (MASC-GP$(n)$), являются $NP$-трудными в сильном смысле. В настоящей работе показано, что данные задачи MAX-SNP-трудны.