Predicate variant of Assignment Problem
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.