Predicate variant of Assignment Problem 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.
Your problem is known as bipartite perfect matching. Unfortunately, the query complexity of your problem is $n^2$ (where $n = |P| = |E|$), that is, in the worst case you might need to make a lot of queries of the form $p(e)$. The complexity remains $n^2$ even if you are allowed XOR queries, and remains $\Omega(n^2)$ even if you are allowed AND queries, or if you are allowed OR queries. See Gal Beniamini and Noam Nisan, Bipartite Perfect Matching as a Real Polynomial.