Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR18-020 | 30th January 2018 08:33

#### Computing the maximum using \$(\min, +)\$ formulas

TR18-020
Authors: Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari
Publication: 30th January 2018 08:56
Keywords:

Abstract:

We study computation by formulas over \$(min, +)\$. We consider the computation of \$\max\{x_1,\ldots,x_n\}\$
over \$\mathbb{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.

### Comment(s):

Comment #1 to TR18-020 | 27th March 2018 10:52

#### (Min, Plus) is Not stronger than (Or, And)

Comment #1
Authors: Stasys Jukna
Accepted on: 27th March 2018 10:52
Keywords:

Abstract:

We observe that a known structural property of (min,+) circuits (and formulas) implies that lower bounds on the monotone circuit/formula size remain valid also for (min,+) circuits, even when only nonnegative integer weights are allowed. So, the lower bound proved in ECCC TR18-020 can be alternatively derived from known lower bounds on the monotone formula complexity of the threshold-2 function.

ISSN 1433-8092 | Imprint