I apologize in advance if this sounds vague but I am trying to find directions as to what to look for.


All the sets in this problem are finite.
Suppose we have two functions $f\_1\colon X\_1\times Y\_1\to X\_1$ and $f\_2\colon X\_2\times Y\_2\to X\_2$.


**Problem**. Decide whether there exist two surjective mappings $p\colon X\_2\to X\_1$ and $q\colon Y\_2\to Y\_1$ satisfying the condition
$$
\forall x\in X\_2, y\in Y\_2 : p(f\_2(x,y))= f\_1(p(x), q(y))
$$


I looked into set-valued optimization and combinatorial set theory but it all seemed too complex for my problem. I have just started reading Kuratowski and Aubin's books. It looks like most optimization problems are formulated using differential inclusion one way or the other and that doesn't seem to be feasible in my case. To me it looks like a typical search problem, I am just not sure how to properly pose it using sets/mappings as variables. Any advice would be super helpful. I am looking into developing an algorithm that proves the existence of the mappings in polynomial time.



Search algorithms with mappings/functions/sets as variables
You can solve the problem via integer linear programming as follows. Let binary decision variables $P(x\_2,x\_1)$ and $Q(y\_2,y\_1)$ indicate whether $p(x\_2)=x\_1$ and $q(y\_2)=y\_1$, respectively. The constraints are:
\begin{align}
\sum\_{x\_1 \in X\_1} P(x\_2,x\_1) &= 1 &&\text{for $x\_2 \in X\_2$} \tag1 \\
\sum\_{y\_1 \in Y\_1} Q(y\_2,y\_1) &= 1 &&\text{for $y\_2 \in Y\_2$} \tag2 \\
\sum\_{x\_2 \in X\_2} P(x\_2,x\_1) &\ge 1 &&\text{for $x\_1 \in X\_1$} \tag3 \\
\sum\_{y\_2 \in Y\_2} Q(y\_2,y\_1) &\ge 1 &&\text{for $y\_1 \in Y\_1$} \tag4 \\
P(x,x\_1) + Q(y,y\_1) - 1 &\le P(f\_2(x,y),f\_1(x\_1, y\_1))
 &&\text{for $x\in X\_2, x\_1\in X\_1, y\in Y\_2, y\_1\in Y\_1$} \tag5
\end{align}
Constraints $(1)$ and $(2)$ enforce that $p$ and $q$ are functions.
Constraints $(3)$ and $(4)$ enforce that $p$ and $q$ are surjective.
Constraint $(5)$ enforces
$$(p(x)=x\_1 \land q(y)=y\_1) \implies p(f\_2(x,y)) = f\_1(x\_1, y\_1)$$


