I have a decision problem that is clearly in NP, but I cannot seem to prove that it is in P, nor can I prove its NP-hardness. I attribute this more to my inexperience than to the problem's difficulty (or its being a candidate for the class of problems that are neither NP-complete nor in P).
An instance of the problem consists of two vectors of positive integers $(d_1,...,d_n)$ and $(a_1,...,a_n)$, along with two positive integers $k$ and $h$. The decision problem is: given $(d_1,...,d_n)$, $(a_1,...,a_n)$, $k$, and $h$, does there exist a multiset $M$ that is $k$-good for $U$ with $|M|=h$? Necessary definitions are below.
Define the set system $U$ as follows. A set $S$ is in $U$ if and only if $S=s_1 \times s_2 \times ... \times s_n$ for some $\{s_i\}$ such that, for all $1\leq i\leq n$, we have $s_i\subseteq \{1,...,d_i\}$ and $|s_i|=a_i$. Let a multiset $M$ be called ``$k$-good for $U$'' if $m\in M \implies m\in U$ and $\forall M'\subseteq M(|M'|=k\implies \bigcap_{m\in M'} m=\emptyset).$ That is to say, $M$ is $k$-good for $U$ iff it is a list (possibly with repetition) of elements of $U$ such that any $k$ elements on the list have empty intersection.
