In the paper *Faster Algorithms for Max-Product Message Passing* by McAuley and Caetano (see e.g. [here](https://cseweb.ucsd.edu/~jmcauley/pdfs/jmlr11.pdf) or [here](https://arxiv.org/abs/0910.3301)), several statements are made which seem mathematically questionable to me.


For completeness sake some of the relevant quotes are included below, but my main point is this:


To the best of my knowledge, 'tropical' (at least in '[tropical geometry](https://mathoverflow.net/questions/83624/why-tropical-geometry)') refers to either the [max-plus algebra](https://en.wikipedia.org/wiki/Tropical_geometry) or the [min-plus algebra](https://math.berkeley.edu/~bernd/mathmag.pdf), such that [tropical matrix multiplication](https://en.wikipedia.org/wiki/Min-plus_matrix_multiplication) corresponds to the [shortest-path problem](https://en.wikipedia.org/wiki/Shortest_path_problem), and, e.g. Dijkstra's or the Floyd-Warshall algorithm


The authors of the paper seem to implicitly be stating that results in the max-plus, min-plus algebras are equivalent to results in the max-product and min-product algebras.


**Question:** Why should we expect that to be true? I.e., is there ***not*** any "fundamental" distinction between min-plus, max-plus, min-product, and max-product algebras? And if not, why not?


Sure, we can derive all four from the min-plus algebra using multiplication by -1 or "tropical exponentiation" (i.e. iterated addition i.e. multiplication), but why should these operations preserve the essential structure of the min-plus algebra? What is the obvious point I am missing?



> 
> Thus our results certainly apply to the max-sum and min-sum (‘tropical’) semirings (as well as max-product and min-product, assuming non-negative potentials)...
> 
> 
> ... message-passing becomes some variant of matrix multiplication. Finally we shall
>  explore other applications besides message-passing that make use of tropical matrix multiplication
>  as a subroutine, such all-pairs shortest-path problems.
> 
> 
> our algorithm is closely related to a well-studied problem known
>  as ‘tropical matrix multiplication’ (Kerr, 1970).
> 
> 
> the problem of matrix-matrix multiplication in the max-product semiring
>  (often referred to as ‘tropical matrix multiplication’, ‘funny matrix multiplication’, or simply ‘maxproduct
>  matrix multiplication’)
> 
> 
> 


*(Note: I'm not sure if this is the right place to ask this question. If it is not, please tell me, so the question can be deleted. Please don't hesitate to suggest a better place to ask it either.)*


**EDIT:** Qiaochu Yuan's correct answer is also corroborated by the paper, *The Generalized Distributive Law*, by Aji and McEliece (2000), which states on p.3 that all four of the above commutative semirings are isomorphic to one another, using (essentially) the same isomorphisms as stated by Qiaochu Yuan in his correct answer.



Is there any "fundamental" distinction between min-plus, max-plus, min-product, and max-product algebras?
Consider the following four semirings, listed in the order underlying set, addition, additive identity, multiplication, multiplicative identity:


1. $A = (\mathbb{R} \cup \{ \infty \}, \text{min}, \infty, +, 0)$
2. $B = (\mathbb{R} \cup \{ - \infty \}, \text{max}, -\infty, +, 0)$
3. $C = (\mathbb{R}\_{> 0} \cup \{ \infty \}, \text{min}, \infty, \times, 1)$
4. $D = (\mathbb{R}\_{\ge 0}, \text{max}, 0, \times, 1)$.


These semirings are all isomorphic. Explicit isomorphisms are as follows:


$$A \ni a \mapsto -a \in B$$
$$A \ni a \mapsto \exp(a) \in C$$
$$C \ni c \mapsto \frac{1}{c} \in D.$$


Is it clear now? 


