Skip to content

Selected-OR Selector Is Not Hidden-Vertex Graph-Cut Expressible

Claim/Theorem

The ternary selector

\[ g(u,C,D):=(1-u)C+uD \qquad (u,C,D)\in\{0,1\}^3 \]

is not expressible by binary submodular functions with auxiliary variables. Equivalently, g is not an ordinary hidden-vertex graph-cut function for any auxiliary budget.

This is a derived obstruction statement.

By [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]], every Boolean function representable by binary submodular functions with auxiliaries must itself be submodular on the visible variables.

So it is enough to show that g is not submodular. Restrict to the face C=0. Then

\[ g(0,0,1)=0,\qquad g(1,0,0)=0, \]

while

\[ g(0,0,0)=0,\qquad g(1,0,1)=1. \]

Hence on the pair of visible assignments

\[ x=(0,0,1),\qquad x'=(1,0,0), \]

one gets

\[ g(x)+g(x')=0 < 1= g(x\wedge x')+g(x\vee x'). \]

This violates submodularity. Therefore g cannot belong to the hidden-vertex binary-submodular expressive class.

Consequently, any representation of the connected multi-parallel-circuit family that factors only through the compressed state (u,C,D) already fails at the selector layer, regardless of how many auxiliary vertices are allowed.

Dependencies

  • [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]]

Conflicts/Gaps

  • This node rules out only the compressed selector route, not every possible hidden-vertex realization of the full connected family.
  • A more global construction could still represent the whole multi-parallel-circuit family without factoring through the ternary selector g.
  • Even a whole-family nonexpressibility theorem would still need a separate argument to connect hidden-vertex failure to routing-style compiler-native semantics.

Sources

  • 10.1016/j.dam.2009.07.001
  • 10.1007/s10878-017-0136-y