Compatible partial permutations
We can reduce it to the following problem:


  Given a directed graph on vertex set $\{1,2,\dots,n\}$, we want to know if there exists a permutation $T$ such that for each edge $(i,j)$ in the graph, $T[i]&lt;T[j]$.


The reduction: add an edge to the graph for each pair $i,j$ where both $P_b[i]$ and $P_b[j]$ exist for some $b \in \{0,1\}$; the orientation of the edge is determined by whether $P_b[i]&lt;P_b[j]$ or not.  This yields a directed graph that contains the union of edges from $P_0$ plus edges from $P_1$.

Conveniently, the new problem is easy.  Of course, if there are any cycles in the graph, then there is no such permutation $T$ (i.e., the two permutations $P_0,P_1$ are not compatible).  Conversely, if there are no cycles in the graph, then there is such a permutation $T$ (i.e., the permutations $P_0,P_1$ are compatible).  Do you see why?  We can simply apply a topological sort to the graph and use it to construct an example of such a permutation $T$, where we assign $T[i]=j$ if vertex $i$ is the $j$th vertex to be visited in the topologically sorted order.

I'm not sure what BDDs have to do with it.  This does not seem like a research-level question.