finding permutations which fulfills given conditions
Jukka's comment reminds me of the following reference.

If we look at such a function g as a matrix, the condition is equivalent to one in the definition of a permuted inverse Monge matrix.  There is a polynomial-time algorithm to determine if a given matrix is a permuted inverse Monge matrix (and if so, that gives corresponding permutations).

The result was found by Deineko and Filonenko (1979) in their Russian paper, and it is explained (in a more general form) in the following survey by Burkard et al.


Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf: Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics 70(2): 95-161 (1996) http://dx.doi.org/10.1016/0166-218X(95)00103-X