The average size of a minimum defining set

Let \(\varphi\) be a propositional logic formula in variables \(\{x_1,...,x_n\}\). Let \(A\) be a binary matrix whose rows are the satisfying assignments of \(\varphi\). One of those satisfying assignments \(v_0\) is the reality of \(\varphi\). There are players 1 and 2. Player 1 knows \(\varphi\) and \(A\) and \(v_0\) and player 2 knows only \(\varphi\) and \(A\). Player 1 sends to player 2 every round the value \(v_0(x_i)\). The goal is for player 1 to send as few values as possible such that player 2 figures out \(v_0\).

Say there are \(m\) satisfying assignments for \(\varphi\). Then the average number of messages needed to be sent, averaged over all satisfying assignments is at most \(\min(\log m,n)\), and this is tight.

\(\min(\log m,n)\).