Finite communication problem and protocol model

A finite communication problem consists of nonempty finite input sets $X,Y$, disjoint sets $YES,NO\subseteq X\times Y$ with nonempty promise $P=YES\cup NO$, and a required output bit on promised pairs. This is the finite-relation generalization of a binary-string promise problem (Promise problem): choose fixed injective labels $c_X:X\to \{0,1{\}}^{\ast }$ and $c_Y:Y\to \{0,1{\}}^{\ast }$, and encode a pair by $e(x,y):=1^{\mathrm{\mid }{c}_X(x)\mathrm{\mid }}0c_X(x)c_Y(y)\mathrm{.}$ The unary length prefix makes $e$ injective, so $e(YES)$ and $e(NO)$ are disjoint subsets of $\{0,1{\}}^{\ast }$. This encoding only formalizes the relation; it is not a transmitted message or part of communication cost unless a protocol explicitly sends it. A protocol specifies who receives each input, the message schedule and number of rounds, each message alphabet or finite-dimensional register (Finite registers and their ordered computational bases), the local maps that produce messages, the referee's finite POVM (Finite POVMs and their outcome law) and output rule, and any shared randomness or entanglement. A quantum message state is a density operator, meaning nonnegative with trace one (Density operator). Its worst-case error is the supremum of the probability of a wrong output over promised input pairs; its communication cost is the maximum total number of transmitted bits or qubits on any promised input. Local computation, referee computation, and shared resources are separately declared and are not silently included in that communication count.

In a simultaneous-message protocol (SMP), Alice and Bob each send one message to a referee without seeing the other's message. For classical private-coin SMP with no shared resource, conditional on inputs $x,y$ the two messages are independent, so their joint law is a product of their individual message distributions. For quantum SMP with no shared entanglement or randomness, the received state is a product of the two locally prepared density operators. These factorization properties are part of the stated resource model.