Why is the hitting set problem in NP

Question

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$?

Answer 1

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)$.