Given two equally sized sets, $P$ of Boolean predicates and $E$, I want to decide if there exists a bijective function $f: P rightarrow E$, such that

begin{align}

forall p in P ; p(f(p))

end{align}

It seems like a special case of having a weight matrix $W$ where $w_{ij}=0$ if $P_i(T_j)$ and otherwise $1$, and then solving the general Assignment Problem.

For practical reasons calculating such a weight matrix up front is not desirable, as evaluating $p$ is not necessarily cheap.

I have also thought about whether it could be formulated as some variant of Stable Marriage Problem, where the men have a predicate that needs to satisfied instead of a ranked preference list over all women.

I don’t think the proposed problem sounds very exotic, so I might just be looking in a wrong direction.