I just started reading Vazirani's book Approximation Algorithms. It is legally available online here.On page 5 (23 in the pdf), it says that the following decision problems are in NP:Is the size of the minimum vertex cover in $G$ at most $k$?Is the size of the maximum matching in $G$ at least $l$?I can't see why this is true. If, say, the first problem is in NP, then each valid instance (graph) has a Yes certificate which proves that the graph has a minimum vertex cover of size at most $k$.But, how can one deduce from a certificate something regarding the size of the minimum vertex cover?
How are these problem variants that ask about the size of optimal solutions in NP?
complexity theory;decision problem;np