# Why is the hitting set problem in NP

I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979):

INSTANCE: Collection $$C$$ of subsets of a set $$S$$, a positive integer $$K$$.

QUESTION: Does $$S$$ contains a hitting set for $$C$$ of size $$K$$ or less, that is, a subset $$S' \subseteq S$$ with $$|S'| \leq k$$ and such that $$S'$$ contains at least one element from each subset in $$C$$?

The problem definitions from other sources (none of which elaborates on the size of $$C$$ in relation to $$|S|$$):

https://theory.stanford.edu/~virgi/cs267/lecture5.pdf

http://cs.indstate.edu/~arash/algo2lec8.pdf

http://www.et.byu.edu/~jka/521/slides/lecture22.pdf

http://www.cs.toronto.edu/~lalla/373s14/assignments/A3Sol.pdf

http://www.cse.iitd.ernet.in/~amitk/SemI-2015/tut12.pdf

Given a set $$S$$ with $$|S| = n$$, a collection $$C$$ of its subsets can have up to $$2^n$$ elements (where each element is a subset of $$S$$).

Given a certificate, $$S' \subseteq S$$, of the Hitting Set Problem, how could we possibly check if $$S'$$ contains at least one element from each subset in $$C$$ in polynomial time w.r.t $$n$$?

You cannot check, in general, whether $$S'$$ contains at least one element from each subset $$C$$ in polynomial time w.r.t. $$n$$.
However, in order to show that the problem is NP it suffices to show that you can check to above condition in polynomial time w.r.t. the instance size, which is in $$\Omega( \sum_{X \in C} |X| + \log n)$$.