Can we decide whether a permanent has a unique term? Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)}$?

Remarks. One can of course replace the product with a sum, the problem stays the same.

If the matrix can have only 0/1 entries, then we get the Bipartite-UPM problem which is even in NC.

Edit: Deciding whether the smallest term is unique is in P as it is equivalent to the minimum weight matching problem, as pointed out by Neal Young in a (since then removed) comment.

Edit: Similar questions:

In an edge-weighted graph, is there a Hamiltonian-cycle with a unique weight?

If we have a CNF with weights assigned to every variable/satisfying assignmet, is there a unique weight satisfying assignment?

These are of course at least NP-hard. Are these problems equivalent to the original or are they harder?
Nice problem!  It's not hard to give a reduction showing that, if one could solve your problem, then one could also solve the following problem, call it ISOLATED SUBSET SUM:

Given integers a1,...,an, is there a subset S of the ai's whose sum is not shared by any other subset?

The reduction works by first reducing ISOLATED SUBSET SUM to ISOLATED PERFECT MATCHING, where given a weighted bipartite graph G, we want to find a perfect matching whose weight isn't shared by any other perfect matching.  This reduction is simple: for each i, create a 2x2 complete subgraph Gi in G, such that which of the two possible matchings we choose for Gi encodes our choice of whether or not ai is in the set S.

Next, reduce ISOLATED PERFECT MATCHING to your problem as follows:


For all i,j, if the edge (i,j) exists and has weight wij, then set Mij:=exp(wij).  (This turns the sums into products.)
For all i,j, if the edge (i,j) doesn't exist, then set Mij:=0.
Pad M to make sure that there are two or more permutations &pi; such that &Pi; Mi,&pi;(i) = 0.  (This rules out spurious solutions that don't correspond to any perfect matching in G.)


Now, ISOLATED SUBSET SUM certainly feels like it's at least NP-hard, and maybe it's even harder than that (the obvious upper bound is only &Sigma;2P)!  Furthermore, perhaps one could prove that ISOLATED SUBSET SUM is NP-hard using a Valiant-Vazirani-style randomized reduction.  This, however, is a challenge I leave to someone else...