1
$\begingroup$

I know that the hitting problem is NP hard, but is it possible to find the magnitude of the smallest set? Also, provide the runtime.

$\endgroup$
  • $\begingroup$ welcome to CS! What have you tried? $\endgroup$ – Yamar69 Oct 24 '19 at 7:26
1
$\begingroup$

When we say that hitting set is NP-hard, we mean that the following decision problem is NP-hard: given a set system $S$ and an integer $k$, decide whether there is a hitting set for $S$ of size at most $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.