16
$\begingroup$

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 NP-hard if we allow randomized reductions. In fact, I originally wanted to pose this question, because it would have helped to solve this one. Now it turned out that this is NP-complete, so let me sketch the reduction to our problem. Imagine that the input is a zero-one matrix (we can suppose that) and replace the zero entries with random real numbers between 2 and 2+1/n. Now in this new matrix with high probability the smallest term is unique if and only if the original matrix is permutable to upper-triangular form.

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?

$\endgroup$
  • $\begingroup$ Do we know if this problem is even in NP? I'm having difficulty coming up with a certificate. $\endgroup$ – mhum Oct 14 '10 at 1:01
  • $\begingroup$ @mhum: The most obvious upper bound is $\Sigma_2 P$, as Scott Aaronson pointed out in his answer. I do not think any better upper bound is known. $\endgroup$ – Joshua Grochow Oct 14 '10 at 1:06
13
$\begingroup$

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:

  1. 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.)
  2. For all i,j, if the edge (i,j) doesn't exist, then set Mij:=0.
  3. Pad M to make sure that there are two or more permutations π such that Π Mi,π(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 Σ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...

$\endgroup$
  • $\begingroup$ Yes, these are equivalent. In fact, if you check the open problem I am trying to solve, you can see that I am coming from the ISOLATED PERFECT MATCHING problem. Maybe one could find a reduction to/from the Frobenius Coin problem. $\endgroup$ – domotorp Oct 10 '10 at 6:16
  • 4
    $\begingroup$ Duhhh ... Andy Drucker helpfully pointed out that my ISOLATED SUBSET SUM problem is trivial to solve! If some of the a_i's are 0, then there's no unique sum; otherwise, take the set of all a_i's sharing the same sign (either positive or negative). So, we should focus on ISOLATED PERFECT MATCHING. $\endgroup$ – Scott Aaronson Oct 10 '10 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.