Computing the maximum using ( min + ) formulas

摘要

We study computation by formulas over ( min + ) . We consider the computation of max x 1 x n over N as a difference of ( min + ) formulas, and show that size n + n log n is sufficient and necessary. Our proof also shows that any ( min + ) formula computing the minimum of all sums of n ? 1 out of n variables must have n log n leaves; this too is tight. Our proofs use a complexity measure for ( min + ) functions based on minterm-like behaviour and on the entropy of an associated graph.