Abstract:
It is known that the problem on the minimal covering of a finite number of points in a plane by a set of straight lines (MIN-PC) and the problem on the minimal affine separating committee formulated in a space of fixed dimension (MASC-GP$(n)$) are NP-hard in the strong sense. We show that these problems are MAX-SNP-hard.
Keywords:computational complexity, strong NP-hardness, covering of points, affine committee.