Minimize function on permutations
Hamiltonian path is a special case of your problem. Given a graph $G$, let $f(n,m) = 1$ if the edge $(n,m)$ exists, and $f(n,m) = 2$ otherwise. The minimum value of $g(\sigma)$ equals 1 iff $G$ contains a Hamiltonian path.