Before revision:  The second is the  -hard problem Line Cover , which asks for a set of k lines that cover the points of S, for a given parameter k \in N. Both problems have been extensively studied.
After revision:  The second is the  -hard problem NP-hard problem Line Cover , which asks for a set of k lines that cover the points of S, for a given parameter k \in N. Both problems have been extensively studied.