<p>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:</p>

<p><i>Given integers a<sub>1</sub>,...,a<sub>n</sub>, is there a subset S of the a<sub>i</sub>'s whose sum is not shared by any other subset?</i></p>

<p>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 G<sub>i</sub> in G, such that which of the two possible matchings we choose for G<sub>i</sub> encodes our choice of whether or not a<sub>i</sub> is in the set S.</p>

<p>Next, reduce ISOLATED PERFECT MATCHING to your problem as follows:</p>

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

<p>Now, ISOLATED SUBSET SUM certainly <i>feels</i> like it's at least NP-hard, and maybe it's even harder than that (the obvious upper bound is only &Sigma;<sub>2</sub>P)!  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...</p>

CC BY-SA 4.0
2020-02-03T15:17:51.023Z
The reduction to ISOLATED PERFECT MATCHING, as described above, isn't necessarily polynomial time.  Using standard encodings, it increases the encoding sizes of the weights exponentially.
Neal Young
CC BY-SA 2.5
2010-10-10T06:16:53.433Z
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.
domotorp
CC BY-SA 2.5
2010-10-10T20:05:09.790Z
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.
Scott Aaronson
CC BY-SA 2.5
2010-10-10T03:14:15.180Z
2010-10-10T03:14:15.180Z
Scott Aaronson
<p><em>EDIT - 2/11/20 - barring mistakes, this should answer the posted question.</em></p>

<p><strong>Summary.</strong> Define a new complexity class, UW-NP, containing languages definable as follows: given any poly-time non-deterministic Turing Machine <span class="math-container">$M$</span>, define its language <span class="math-container">$L(M)$</span> to be the set of inputs <span class="math-container">$x$</span> to <span class="math-container">$M$</span> such that, among all non-deterministic executions of <span class="math-container">$M$</span> on input <span class="math-container">$x$</span>, there is at least one whose output is unique (where the output is, say, the contents of the tape when the execution halts).</p>

<p>All of the problems considered in the post are clearly in UW-NP.  To answer the post, we will argue that they are all complete for UW-NP under poly-time reductions, and therefore all poly-time reduce to each other.  We do this with a series of reductions, some involving new problems that we introduce for convenience.</p>

<hr>

<h1>Isolated Perfect Matching</h1>

<p>This section proves the following theorem:</p>

<p><strong>Theorem 1.</strong> <em>Unique-Weight SAT (as defined at the end of OP's post) reduces in polynomial time to Isolated Perfect Matching (as defined in Scott Aaronson's answer).</em></p>

<p>We'll start by showing that the following technically convenient problem reduces to Isolated Perfect Matching:</p>

<p><strong>Definition 1.</strong> Define <em>Unique Subset Sum from Collection (USSC)</em> as follows.
The input is a collection <span class="math-container">$C$</span> of sequences of non-negative integers.
(That is, each <span class="math-container">$a\in C$</span> is of the form <span class="math-container">$a=(a_1, a_2, \ldots, a_\ell)$</span> where each <span class="math-container">$a_i$</span> is a non-negative integer).
The question is whether there is a subsequence of any of the given sequences whose sum is unique
(among all subsequences of all sequences <span class="math-container">$a\in C$</span>).</p>

<p><strong>Lemma 1.</strong> <em>There is a polynomial-time reduction from USSC to Isolated Perfect Matching.</em></p>

<p><em>Proof.</em> Given <span class="math-container">$C$</span>, the reduction outputs an edge-weighted bipartite graph with the following key property: <em>for each subsequence <span class="math-container">$S$</span> of each sequence <span class="math-container">$a\in C$</span>, there is exactly one perfect matching in the graph whose non-zero edge weights are the weights in <span class="math-container">$S$</span>
(and all perfect matchings in the graph can be obtained this way for some such <span class="math-container">$S$</span>).</em>  This property ensures that the reduction is correct.</p>

<p>The construction is best explained by example.
It is shown below for three sequences <span class="math-container">$a, b, c$</span> each of length <span class="math-container">$4$</span>.
(This construction is inspired by Figure 1 of <a href="https://doi.org/10.1145/12130.12136" rel="nofollow noreferrer">A. Broder's paper</a> on approximation of the permanent, which shows an example attributed to Jorge Stolfi.)
Part (a) shows the full graph.  All unlabeled edges have weight zero.
Part (b) shows a matching (the solid edges) whose weights correspond to the subsequence <span class="math-container">$(b_1, b_4)$</span> of <span class="math-container">$b$</span>.</p>

<p><a href="https://i.sstatic.net/285H9.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/285H9.png" alt="enter image description here"></a></p>

<p>The graph has a "row" for each sequence in the collection.
(In the example, the row for <span class="math-container">$a$</span> consists of the nodes 01-09 and 10-18.
The row for <span class="math-container">$b$</span> consists of the nodes 21-29 and 30-38. 
The row for <span class="math-container">$c$</span> consists of the nodes 41-49 and 50-58.)</p>

<p>Consider any perfect matching of the graph.
Each row is composed of 4-cycles (e.g. <span class="math-container">$(01, 12, 02, 11)$</span>) each with two "external" edges leaving the 4-cycle.
Because each 4-cycle has an even number of nodes, in any perfect matching, either both of the external edges (leaving the 4-cycle) are in the matching, or neither are.  It follows that, within each row, either all the external edges are in the matching or none are.  In the former case, each 4-cycle has two nodes matched by its two external edges, so the remaining two nodes must be matched (together) by the single zero-weight diagonal edge connecting them.  (See the first row in Part (b) of the figure.)  So, within the row, the matching is forced to use only zero-weight edges.</p>

<p>In the remaining case (in the row, none of the external edges are in the matching), within each 4-cycle, there are two matched edges --- either the two diagonal zero-weight edges, or the two vertical edges, whose weights are zero and one of the elements in the row's sequence.  It follows that the weights of the matched edges in the row consist of any subsequence of the row's sequence, together with some zeros.  (See the second row in Part (b) of the figure, in which there are matched edges for <span class="math-container">$b_1$</span> and <span class="math-container">$b_4$</span>, together with some zero-weight edges.)  In this way, the possible matched edges within the row correspond bijectively with the possible subsequences of the row's sequence.</p>

<p>Finally, because of the edges to the <span class="math-container">$L$</span> and <span class="math-container">$R$</span> nodes (each of which must have one matched edge), exactly one of the rows (the top row for <span class="math-container">$a$</span>, the middle row for <span class="math-container">$b$</span>, or the bottom row, for <span class="math-container">$c$</span>) is in the "unforced" state, while the other two must be forced to use only zero edges.</p>

<p>In this way, we see the graph has the desired property:
for each subsequence <span class="math-container">$S$</span> of each sequence <span class="math-container">$a\in C$</span>,
there is exactly one perfect matching in the graph whose non-zero edge weights are the weights in <span class="math-container">$S$</span>
(and all perfect matchings in the graph can be obtained this way for some such <span class="math-container">$S$</span>).  Hence the reduction is correct. <span class="math-container">$~~\Box$</span></p>

<hr>

<p>Next we describe a reduction from Unique-Weight Subset Sum (defined next) to USSC (as defined above).</p>

<p><strong>Definition 2.</strong>  Define <em>Unique-Weight Subset Sum</em> as follows.  The input is a triple <span class="math-container">$(x, T, y)$</span> where <span class="math-container">$(x, T)$</span> is a standard Subset-Sum instance (so <span class="math-container">$x=(x_1, x_2, \ldots, x_n)$</span> is a sequence of non-negative integers and <span class="math-container">$T$</span> is the target) and <span class="math-container">$y=(y_1,\ldots, y_n)$</span> is another sequence of non-negative integers.  We call <span class="math-container">$x_1, \ldots, x_n$</span> the <em>primary weights</em> and <span class="math-container">$y_1,\ldots, y_n$</span> the <em>secondary</em> weights.  The question is whether, among the subsequences of <span class="math-container">$x$</span> that sum to <span class="math-container">$T$</span>, there is one such that the sum of the corresponding secondary weights is unique (among all subsets of <span class="math-container">$x$</span> that sum to <span class="math-container">$T$</span>).  Formally, among all index sets <span class="math-container">$S\subseteq \{1,2,\ldots,n\}$</span> such that <span class="math-container">$\sum_{i\in S} x_i = T$</span>, is there one where <span class="math-container">$\sum_{i\in S} y_i$</span> is unique?  (If there are no such subsequences summing to <span class="math-container">$T$</span>, the answer is no.)</p>

<p><strong>Lemma 2.</strong> <em>Unique-Weight Subset Sum reduces to USSC</em>.</p>

<p><em>Proof.</em> Here is the reduction.
Fix an instance <span class="math-container">$(x, T, y)$</span> of Unique-Weight Subset Sum, with primary weights <span class="math-container">$x=(x_1, x_2, \ldots, x_n)$</span>, target <span class="math-container">$T$</span>,
and secondary weights <span class="math-container">$y=(y_1, \ldots, y_n)$</span>.
Assume without loss of generality that <span class="math-container">$T=2^k$</span> for some integer <span class="math-container">$k$</span> such that <span class="math-container">$\sum_i x_i &lt; 2^{k+1}$</span>.  (Otherwise, for <span class="math-container">$k$</span> such that <span class="math-container">$\sum_i x_i &lt; 2^k$</span>, replace the target by <span class="math-container">$T'=2^{k}$</span> and add <span class="math-container">$x_{n+1} = T'-T$</span> to the collection, with secondary weight <span class="math-container">$y_{n+1}$</span> equal to zero.  This preserves the instance because every subsequence that sums to <span class="math-container">$T'$</span> must include <span class="math-container">$x_{n+1}$</span>.)  </p>

<p>The reduction outputs a USSC instance <span class="math-container">$C=(a, b, c)$</span> as defined below.
First, let <span class="math-container">$d$</span> be the number of bits needed to encode <span class="math-container">$\sum_i y_i$</span> in standard binary representation(so <span class="math-container">$\sum_i y_i &lt; 2^d$</span>).
Recall that <span class="math-container">$\sum_i x_i &lt; 2^{k+1}$</span>, so <span class="math-container">$k+1$</span> bits suffice to encode <span class="math-container">$\sum_i x_i$</span>.
For each <span class="math-container">$i\in \{1,\ldots,n\}$</span>,
take <span class="math-container">$a_i$</span> to be the <span class="math-container">$(1+k+d)$</span>-bit integer that encodes <span class="math-container">$y_i$</span> in its <span class="math-container">$d$</span> least-significant bits,
while encoding <span class="math-container">$x_i$</span> in its <span class="math-container">$k+1$</span> most-significant bits.
That is, take <span class="math-container">$a_i = x_i 2^d + y_i$</span>.</p>

<p>Then, for any <span class="math-container">$S\subseteq\{1,2,\ldots,n\}$</span>, we have
<span class="math-container">$$\sum_{i\in S} a_i ~=~ 2^d \sum_{i\in S} x_i ~+~ \sum_{i\in S} y_i.$$</span>
Further, <span class="math-container">$\sum_{i\in S} y_i$</span> is encoded in the <span class="math-container">$d$</span> least-significant bits of <span class="math-container">$\sum_{i\in S} a_i$</span>,
while <span class="math-container">$\sum_{i\in S} x_i$</span> is encoded in the <span class="math-container">$k+1$</span> remaining (most-significant) bits of <span class="math-container">$\sum_{i\in S} a_i$</span>.</p>

<p>Recall that the question is <em>among <span class="math-container">$S\subseteq\{1,2,\ldots,n\}$</span> such that the primary weights sum to the target (<span class="math-container">$\sum_{i\in S} x_i = T$</span>), is there an <span class="math-container">$S$</span> such that the sum of the secondary weights (<span class="math-container">$\sum_{i\in S} y_i$</span>) is unique?</em></p>

<p>Given the previous considerations, and <span class="math-container">$T=2^k$</span>,
the condition <span class="math-container">$\sum_{i\in S} x_i = T$</span> is equivalent to the condition that, if we encode <span class="math-container">$\sum_{i\in S} a_i$</span> as a <span class="math-container">$(1+k+d)$</span>-bit integer,
the <span class="math-container">$(k+1)$</span> most-significant bits encode <span class="math-container">$T = 2^{k}$</span>.</p>

<p>Thus, the question is equivalent to <em>among <span class="math-container">$S\subseteq \{1,\ldots,n\}$</span>, is there one such that the sum <span class="math-container">$\sum_{i\in S} a_i$</span> is both unique (among all <span class="math-container">$S$</span>), and its <span class="math-container">$k+1$</span> most-significant bits encode <span class="math-container">$2^k$</span>?</em></p>

<p>To capture the latter condition, we will construct <span class="math-container">$b$</span> such that the weights obtainable by summing subsequences of <span class="math-container">$b$</span> are exactly the <span class="math-container">$(1+k+d)$</span>-bit integers whose <span class="math-container">$k+1$</span> most-significant bits do <em>not</em> encode <span class="math-container">$2^k$</span>.  And we will take <span class="math-container">$c=b$</span>, so that all such weights can be obtained in at least two ways (and are therefore not candidates to be unique).  Specifically, we take</p>

<p><span class="math-container">$$b = c = (2^0, 2^1, \ldots, 2^{d+k-1}, 2^{k+d}+2^d).$$</span></p>

<p>Note the final weight has an extra additive <span class="math-container">$2^d$</span>.
Using the weights in <span class="math-container">$b$</span> other than that one, one can make any sum in <span class="math-container">$\{0,1,\ldots,2^{k+d}-1\}$</span>.
Then, by using the last weight in combination with some other weights in <span class="math-container">$b$</span>,
one can make any sum in <span class="math-container">$\{2^{k+d}+2^d, \ldots, 2^{k+d+1}-1\}$</span>.
So, one can make any <span class="math-container">$(1+k+d)$</span>-bit integer except those in the range <span class="math-container">$\{2^{k+d}, \ldots, 2^{k+d}+2^d-1\}$</span>,
that is, except those whose <span class="math-container">$k+1$</span> most-significant bits encode <span class="math-container">$2^k$</span>, as desired.</p>

<p>It follows that there is a unique-weight subsequence of some sequence in <span class="math-container">$C=(a, b, c)$</span>
if and only if the given Unique-Weight Subset Sum instance <span class="math-container">$(x, T, y)$</span> has a subsequence with total primary weight <span class="math-container">$T$</span> and unique total secondary weight.  That is, the reduction is correct.  <span class="math-container">$~~\Box$</span></p>

<hr>

<p>To complete the proof of Theorem 1, we show that Unique-Weight SAT (as defined at the end of OP's post) reduces to Unique-Weight Subset Sum:</p>

<p><strong>Lemma 3.</strong> <em>Unique-Weight SAT reduces to Unique-Weight Subset Sum.</em></p>

<p><em>Proof.</em> Fix an instance <span class="math-container">$(\phi(v), w)$</span> of Unique-Weight SAT.  That is, <span class="math-container">$\phi$</span> is a Boolean formula on Boolean variables <span class="math-container">$v=(v_1, v_2, \ldots, v_m)$</span>, and <span class="math-container">$w=(w_1, \ldots, w_m)$</span> is a vector of non-negative integers, one for each variable.  The question is whether there exists a satisfying assignment to <span class="math-container">$v$</span> such that the sum of the weights of the true variables is unique among all satisfying assignments.</p>

<p>The reduction is the standard reduction from SAT to Subset-Sum, augmented as follows.  Let <span class="math-container">$(x, T)$</span> be the output of the standard reduction from SAT to Subset Sum, given input <span class="math-container">$\phi(v)$</span>.  Following that reduction, the satisfying assignments for <span class="math-container">$\phi$</span> correspond bijectively to subsequences of <span class="math-container">$x$</span> that sum to <span class="math-container">$T$</span>.  Further, for each Boolean variable <span class="math-container">$v_i$</span> in <span class="math-container">$\phi$</span>, there is a weight (WLOG <span class="math-container">$x_i$</span>) in <span class="math-container">$x$</span> such that, for each satisfying assignment to <span class="math-container">$v$</span> and its corresponding subsequence summing to <span class="math-container">$T$</span>, <span class="math-container">$v_i$</span> is true if and only if <span class="math-container">$x_i$</span> is included in the subsequence.  For each such variable <span class="math-container">$v_i$</span>, set <span class="math-container">$y_i=w_i$</span> (that is, the secondary weight of <span class="math-container">$x_i$</span> is the weight of <span class="math-container">$v_i$</span>).  Set the secondary weights of all remaining variables to zero.</p>

<p>This concludes the reduction.  By inspection, the satisfying assignments for <span class="math-container">$\phi$</span> correspond bijectively with the subsequences of <span class="math-container">$x$</span> that sum to <span class="math-container">$T$</span>, and the weight associated with each satisfying assignment equals the secondary weight associated with the corresponding subsequence of <span class="math-container">$x$</span>.  Thus, the reduction is correct.  <span class="math-container">$~~\Box$</span></p>

<p>Lemmas 1-3 directly imply Theorem 1.</p>

<hr>

<h1>Unique Permanent Term</h1>

<p>Next we turn our attention to Unique Permanent Term (the problem defined at the top of OP's post).
The ideas are similar but work with products instead of sums.
First, in this section, we show the following theorem for <em>Unique-Product SAT</em> (the "product" variant of Unique-Weight SAT):</p>

<p><strong>Theorem 2.</strong> <em>Unique-Product SAT (as defined below) reduces in polynomial time to Unique Permanent Term.</em></p>

<p>(In the next section, to complete the answer, we sketch how to reduce Unique-Weight SAT to Unique-Product SAT.) </p>

<p><strong>Definition 3.</strong> <em>Unique Product SAT</em> is the following problem: <em>Given a SAT formula having a positive integer weight associated with each variable, among satisfying assignments for the formula, is there one where the product of the weights of the true variables is unique?</em></p>

<p>We prove Theorem 2 via a series of reductions, similar to the proof of Theorem 1.</p>

<p>We'll start by showing that the following technically convenient problem reduces to Unique Permanent Term:</p>

<p><strong>Definition 4.</strong> Define <em>Unique Subset Product from Collection (USPC)</em> as follows.
The input is a collection <span class="math-container">$C$</span> of sequences of non-negative integers.
The question is whether there is a subsequence of any of the given sequences whose <em>product</em> is unique
(among all subsequences of all sequences <span class="math-container">$a\in C$</span>).</p>

<p><strong>Lemma 4.</strong> <em>There is a polynomial-time reduction from USPC to Unique Permanent Term.</em></p>

<p><em>Proof.</em> We note that Unique Permanent Term is equivalent to the following problem: <em>Given a bipartite graph <span class="math-container">$G=(U, W, E)$</span> with integer edge weights and <span class="math-container">$|U|=|W|$</span>, is there a perfect matching such that the product of the weights of the matched edges is unique (among all perfect matchings)?</em>  We reduce USPC to this problem.</p>

<p>The reduction and its proof are the exactly same as for the proof of Lemma 1 (reduction of USSC to Isolated Perfect Matching)
except that the unlabeled edges instead have weight 1 instead of zero,
and instead of considering sums of subsequences, we use products.  <span class="math-container">$~~\Box$</span></p>

<hr>

<p>Next we show that <em>Unique-Product 3D-Matching</em> (defined below) reduces to USPC.</p>

<p><strong>Definition 5.</strong> <em>Unique-Product 3D-Matching</em> is the following problem:
<em>The input is a triple <span class="math-container">$(X, U, w)$</span> where <span class="math-container">$U$</span> is a universe of elements, <span class="math-container">$X$</span> is a collection of triples of elements in <span class="math-container">$U$</span>,
and <span class="math-container">$w_i$</span>, a positive integer weight, is the weight associated with the <span class="math-container">$i$</span>th triple.
The question is whether, among subsets <span class="math-container">$M$</span> of <span class="math-container">$X$</span> that partition <span class="math-container">$U$</span> (called 3D-matchings) there is one such that the product of the weights of the triples in <span class="math-container">$X$</span> is unique.</em></p>

<p><strong>Lemma 5.</strong> <em>There is a polynomial-time reduction from Unique-Product 3D-Matching to USPC.</em></p>

<p><em>Proof sketch.</em> The reduction is similar in spirit to <a href="https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete">the classical reduction from standard 3D-Matching to the Subset Product problem</a>.
Here is the reduction.  Fix an input <span class="math-container">$(X, U, w)$</span> of Unique-Product 3D-Matching.   Let <span class="math-container">$n=|U|$</span> be the size of the universe.  Assume WLOG that <span class="math-container">$U=\{1,2,\ldots, n\}$</span>.</p>

<p>Let <span class="math-container">$(x_i, y_i, z_i)$</span> denote the <span class="math-container">$i$</span>th triple, with (positive integer) weight <span class="math-container">$w_i$</span>.  Call this weight the <em>primary</em> weight of the triple.</p>

<p>Let <span class="math-container">$p(1), p(2), \ldots, p(n)$</span> be the first <span class="math-container">$n$</span> primes that are relatively prime to every weight <span class="math-container">$\{w_i\}$</span>.
(That is, skip primes that are factors of some weight.
These primes can be found in time polynomial in <span class="math-container">$n$</span> e.g. using the Sieve of Eratosthenes or the AKS algorithm.)
Let <span class="math-container">$P=p(1)\cdot p(2)\cdot \cdots\cdot p(n)$</span> be their product.</p>

<p>Following the standard reduction from 3D-Matching to Subset Product,
associate with each triple <span class="math-container">$(x_i, y_i, z_i)$</span> the product <span class="math-container">$p(x_i)\cdot p(y_i)\cdot p(z_i)$</span>.  Call this product the <em>secondary weight</em> of the triple.</p>

<p>Then a subset <span class="math-container">$M\subseteq X$</span> of the triples forms a 3D-matching (i.e. partitions <span class="math-container">$U$</span>)
if and only if the product of the secondary weights of its elements equals <span class="math-container">$P$</span>.</p>

<p>Hence, the question is: <em>Among subsets of triples whose secondary weights have product <span class="math-container">$P$</span>,
is there one for which the product of the associated primary weights is unique?</em></p>

<p>We construct an instance <span class="math-container">$C$</span> of USPC that answers this question,
proceeding in a similar spirit as in the proof of Lemma 2.</p>

<p>The first sequence in the collection <span class="math-container">$C$</span> is <span class="math-container">$a$</span>,
with an element <span class="math-container">$a_i = w_i\cdot p(x_i)\cdot p(y_i)\cdot p(z_i)$</span> for each of the <span class="math-container">$m$</span> triples.</p>

<p>The question can now be stated as: <em>Among subsequences of <span class="math-container">$a$</span>, is there one whose product is unique,
AND whose product includes each of the <span class="math-container">$n$</span> primes <span class="math-container">$p(1), p(2), \ldots, p(n)$</span> exactly once?</em></p>

<p>To enforce the latter condition, for each of the <span class="math-container">$n$</span> primes <span class="math-container">$p(i)$</span>,
we add <em>two</em> sequences to the collection <span class="math-container">$C$</span>, each with exactly the following elements:</p>

<p><span class="math-container">$$S(i)=\{w_1, w_2, \ldots, w_m\} \cup \Big(\bigcup_j \{p(j)^1, p(j)^2, \ldots, p(j)^m\}\Big) \setminus \{p(i)\}.$$</span></p>

<p>This completes the reduction.</p>

<p>Because we add <em>two</em> sequences with the elements in <span class="math-container">$S(i)$</span> to <span class="math-container">$C$</span>,
none of the subsequences of any such sequence can have a unique product
(among subsequences of sequences in <span class="math-container">$C$</span>).</p>

<p>And for any subsequence of <span class="math-container">$a$</span> that is missing one of the primes <span class="math-container">$p(i)$</span>, or has two or more elements having a factor of <span class="math-container">$p(i)$</span>,
the product of that subsequence is the same as the product of some subsequence of <span class="math-container">$S(i)$</span>,
so its product is not unique.  Conversely, if a subsequence of <span class="math-container">$a$</span> has, for each <span class="math-container">$p(i)$</span>, exactly <em>one</em> element having <span class="math-container">$p(i)$</span> as a factor,
then that subsequence's product has just one factor of each <span class="math-container">$p(i)$</span>, so the product is not the same as the product of any subsequence of any <span class="math-container">$S(i)$</span>.</p>

<p>It follows that there is a unique-product subsequence of one of the sequences in <span class="math-container">$C$</span>
if and only if, among 3D-matchings of the given graph, there is one whose product of weights is unique. <span class="math-container">$~~\Box$</span></p>

<hr>

<p>Finally we reduce <em>Unique-Product SAT</em> (defined above, Definition 3) to Unique-Product 3D-Matching.</p>

<p><strong>Lemma 6.</strong> <em>There is a polynomial-time reduction from Unique-Product SAT to Unique-Product 3D-Matching.</em></p>

<p><em>Proof sketch.</em> The reduction is the standard (parsimonious) reduction from SAT to the standard 3D Matching problem, modified as follows.  That reduction produces a 3D-matching instance <span class="math-container">$(X, U)$</span> whose 3D matchings correspond bijectively to the satisfying assignments of the given formula.  Furthermore, for each variable of the given SAT formula, there is a triple in <span class="math-container">$X$</span> such that, in any satisfying assignment, the variable is true if and only if that triple is in the 3D matching.  For each variable, choose such a triple and give it weight equal to the weight of its variable.  Give all other triples weight 1.  Then the product of the weights for any satisfying assignment equals the product of the weights for the corresponding 3D matching. This implies that the reduction is correct. <span class="math-container">$~~\Box$</span></p>

<p>Theorem 2 follows directly from Lemmas 4--6.</p>

<hr>

<h1>All these problems are complete for UW-NP</h1>

<p>To finish we sketch how Unique-Weight SAT is equivalent to Unique-Product SAT (under poly-time reductions).</p>

<p>To do this, recall the complexity class UW-NP defined at the start of the answer.
(It contains languages definable as follows: given any poly-time non-deterministic Turing Machine <span class="math-container">$M$</span>, its language <span class="math-container">$L(M)$</span> is the set of inputs <span class="math-container">$x$</span> to <span class="math-container">$M$</span> such that, among all non-deterministic executions of <span class="math-container">$M$</span> on input <span class="math-container">$x$</span>, there is at least one whose output is unique, where the output is the contents of the tape when the execution halts.)</p>

<p>Unique-Weight SAT and Unique-Product SAT are clearly in UW-NP.
To show that they are equivalent, we show the following lemma:</p>

<p><strong>Lemma 7.</strong> <em>Unique-Weight SAT and Unique-Product SAT are each UW-NP-complete (under poly-time reductions).</em></p>

<p><em>Proof sketch.</em> First we argue that Unique-Weight SAT is UW-NP-complete.</p>

<p>The basic idea is to modify the standard proof that SAT is NP-complete, by adding weights to the variables of the SAT formula.  In particular, in the standard proof, the SAT formula has, for each tape cell <span class="math-container">$i$</span>, tape symbol <span class="math-container">$\tau$</span> in the tape alphabet <span class="math-container">$\mathcal{T}$</span>, and time <span class="math-container">$t$</span>, a Boolean variable <span class="math-container">$v(i, \tau, t)$</span> that encodes whether tape cell <span class="math-container">$i$</span> contains <span class="math-container">$\tau$</span> at time <span class="math-container">$t$</span>.  If time <span class="math-container">$t$</span> is not the termination time, we give this variable weight zero.  Otherwise we give it weight <span class="math-container">$(j-1)|\mathcal{T}|^i$</span>, where <span class="math-container">$\tau$</span> is the <span class="math-container">$j$</span>th tape symbol in <span class="math-container">$\mathcal{T}$</span>.
This completes the reduction.</p>

<p>Then the non-deterministic execution paths correspond bijectively with the satisfying assignments to the formula,
and the total weight of each satisfying assignment faithfully encodes the output, so the reduction is correct.</p>

<p>(I am waving my hands here a bit -- e.g. in the assumption that all execution paths end at the same time.
I believe such technical details are addressable but getting into them would take us too far afield.) </p>

<p>The proof for Unique-Product SAT is the same except for the assignments of weights to variables.
For Boolean variable <span class="math-container">$v(i, \tau, t)$</span>, if time <span class="math-container">$t$</span> is not the termination time, give the variable weight 1.
Otherwise, give the variable weight <span class="math-container">$p_i^j$</span>, where <span class="math-container">$p_i$</span> is the <span class="math-container">$i$</span>th prime and <span class="math-container">$\tau$</span> is the <span class="math-container">$j$</span>th symbol in the tape alphabet.
(Note that the first <span class="math-container">$n$</span> primes <a href="https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete">can be calculated and encoded in time poly<span class="math-container">$(n)$</span></a>.)
Then the non-deterministic execution paths correspond bijectively with the satisfying assignments to the formula,
and the product of the weights of each satisfying assignment faithfully encodes the output, as desired.
<span class="math-container">$~~\Box$</span></p>

<hr>

<p>By Lemmas 1--7, all of the problems mentioned in this answer are UW-NP-complete, and therefore equivalent under poly-time reductions.  This (barring mistakes) answers the posed question.  (Well, we didn't consider Unique-Weight Hamiltonian Cycle, but it is clearly in UW-NP and can easily be shown UW-NP complete by reduction from Unique-Weight SAT, by adapting the standard reduction from SAT to Hamiltonian Cycle.)</p>

<hr>

<h1>Concluding remarks and questions</h1>

<p>Some observations about how UW-NP relates to existing complexity classes:</p>

<p><strong>Observation 1.</strong> <em>UW-NP contains NP.</em></p>

<p>(For Unique-Weight SAT, the special case when all weights are distinct powers of two is equivalent to regular SAT, because every assignment has a distinct total weight.)</p>

<p><strong>Observation 2.</strong> <em>UW-NP contains the complexity class <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#us" rel="nofollow noreferrer">US</a>.</em></p>

<p>(US contains languages defined as follows: given any non-deterministic poly-time TM, its language contains the inputs for which exactly one execution path accepts.  The restriction of Unique-Weight SAT to instances where all weights are zero is equivalent to the classical <a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT" rel="nofollow noreferrer">Unique SAT problem</a> (<em>"Given a Boolean formula, does it have exactly one satisfying assignment?"</em> --- not to be confused with <em><a href="https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT" rel="nofollow noreferrer">Unambiguous SAT</a></em>, which is the promise problem obtained by restricting SAT to instances where there is at most one satisfying assignment).
Unique SAT (and, via parsimonious reductions, Unique Hamiltonian Cycle) are complete for the complexity class <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#us" rel="nofollow noreferrer">US</a>.</p>

<p>US also contains co-NP (and is contained in <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp" rel="nofollow noreferrer">DP</a>). US is considered unlikely to be equal to co-NP [e.g. <a href="https://doi.org/10.1007/3-540-48321-7_27" rel="nofollow noreferrer">here</a>, <a href="https://doi.org/10.1016/S0019-9958(82)90439-9" rel="nofollow noreferrer">here</a>]. So:</p>

<p><strong>Observation 3.</strong> <em>UW-NP contains co-NP.</em></p>

<p>Is UW-NP contained in <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp" rel="nofollow noreferrer">DP</a>?   It is contained in <span class="math-container">$\Sigma_2$</span>P; is it equal to <span class="math-container">$\Sigma_2$</span>P?</p>

<hr>

<p>What about the problems below?</p>

<ol>
<li><p><em>Given an edge-weighted digraph, does it have a simple <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path whose weight is unique?</em> This seems to be UW-NP-complete (e.g. by reduction from Unique-Weight Hamiltonian Cycle).  The corresponding counting problem (<em>Given a digraph, how many simple <span class="math-container">$s$</span>-<span class="math-container">$t$</span> paths does it have?</em>) <a href="https://doi.org/10.1137/0208032" rel="nofollow noreferrer">is #P-complete</a>.</p></li>
<li><p><em>Given an edge-weighted graph, does it have a spanning tree whose weight is unique?</em>  Is this one UW-NP-complete?  The corresponding counting problem (<em>Given a graph, how many spanning trees does it have?</em>) is in P.</p></li>
<li><p>For all of these problems, instead of asking whether there exists at least one unique-weight object, we could ask whether there exist at least two objects that have the same weight.  These variants are generally in NP, and NP-hard if the underlying search problem is NP-hard (by taking the weights to be zero, essentially).  But what about problems where the underlying search problem is in P, e.g., <em>Given an edge-weighted bipartite graph, are there two perfect matchings with the same weight</em>?</p></li>
</ol>

<hr>

CC BY-SA 4.0
2020-02-13T19:52:09.823Z
I think this has outgrown the size of a cstheory.SE answer...
domotorp
CC BY-SA 4.0
2020-02-14T02:56:39.740Z
I agree it is rather long. The result for Isolated Perfect Matching is short enough, or the reduction from Unique-Product SAT to Unique Permanent Term would be, but I don't see any shorter way of getting from Unique-Weight SAT to any "unique product" problem
Neal Young
CC BY-SA 4.0
2020-02-24T07:04:05.040Z
Uh, yeah, this seems to me like a paper. You should publish it! (Or maybe see if domotorp wants to combine it with whatever led to this question and publish together...)
Joshua Grochow
CC BY-SA 4.0
2020-02-24T07:13:54.187Z
Re: your question about being in DP. It's not even clear to me that it is in [BH](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bh). The issue is that, for the Boolean hierarchy over NP, the languages you are taking Boolean combinations of don't "know about" each other's witnesses, so it seems hard to detect unique outputs in this way. I wonder if it is related to [HNOS](https://doi.org/10.1137/S0097539794268315).
Joshua Grochow
CC BY-SA 4.0
2020-01-31T02:39:41.730Z
2020-02-14T02:58:36.053Z
2020-02-14T02:58:36.053Z
Neal Young
<p>Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation <span class="math-container">$\sigma$</span> such that for all permutations <span class="math-container">$\pi\ne\sigma$</span> we have <span class="math-container">$\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)}$</span>?</p>

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

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

<p>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.</p>

<p>Edit: Similar questions:</p>

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

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

<p>These are of course at least NP-hard. Are these problems equivalent to the original or are they harder?</p>

CC BY-SA 2.5
2010-10-14T01:01:39.640Z
Do we know if this problem is even in NP? I'm having difficulty coming up with a certificate.
mhum
CC BY-SA 2.5
2010-10-14T01:06:00.040Z
@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.
Joshua Grochow
<cc.complexity-theory><ds.algorithms><matrices><matching><permanent>
Can we decide whether a permanent has a unique term?
domotorp
# Can we decide whether a permanent has a unique term?

(Asked by: username_0 on 2010-10-08)

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 username_4 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?

**Tags:** cc.complexity-theory, ds.algorithms, matrices, matching, permanent

> **Comments:**
> **username_1**: Do we know if this problem is even in NP? I'm having difficulty coming up with a certificate.  
> **username_2**: @username_1: The most obvious upper bound is $\Sigma_2 P$, as username_3 pointed out in his answer. I do not think any better upper bound is known.  

---

## 2 answers

### Answer by username_4 on 2020-01-31. Score: 7 | Accepted answer

*EDIT - 2/11/20 - barring mistakes, this should answer the posted question.*

**Summary.** Define a new complexity class, UW-NP, containing languages definable as follows: given any poly-time non-deterministic Turing Machine $M$, define its language $L(M)$ to be the set of inputs $x$ to $M$ such that, among all non-deterministic executions of $M$ on input $x$, there is at least one whose output is unique (where the output is, say, the contents of the tape when the execution halts).

All of the problems considered in the post are clearly in UW-NP. To answer the post, we will argue that they are all complete for UW-NP under poly-time reductions, and therefore all poly-time reduce to each other. We do this with a series of reductions, some involving new problems that we introduce for convenience.

---

# Isolated Perfect Matching

This section proves the following theorem:

**Theorem 1.** *Unique-Weight SAT (as defined at the end of OP's post) reduces in polynomial time to Isolated Perfect Matching (as defined in username_3's answer).*

We'll start by showing that the following technically convenient problem reduces to Isolated Perfect Matching:

**Definition 1.** Define *Unique Subset Sum from Collection (USSC)* as follows.
The input is a collection $C$ of sequences of non-negative integers.
(That is, each $a\in C$ is of the form $a=(a\_1, a\_2, \ldots, a\_\ell)$ where each $a\_i$ is a non-negative integer).
The question is whether there is a subsequence of any of the given sequences whose sum is unique
(among all subsequences of all sequences $a\in C$).

**Lemma 1.** *There is a polynomial-time reduction from USSC to Isolated Perfect Matching.*

*Proof.* Given $C$, the reduction outputs an edge-weighted bipartite graph with the following key property: *for each subsequence $S$ of each sequence $a\in C$, there is exactly one perfect matching in the graph whose non-zero edge weights are the weights in $S$
(and all perfect matchings in the graph can be obtained this way for some such $S$).* This property ensures that the reduction is correct.

The construction is best explained by example.
It is shown below for three sequences $a, b, c$ each of length $4$.
(This construction is inspired by Figure 1 of [A. Broder's paper](https://doi.org/10.1145/12130.12136) on approximation of the permanent, which shows an example attributed to Jorge Stolfi.)
Part (a) shows the full graph. All unlabeled edges have weight zero.
Part (b) shows a matching (the solid edges) whose weights correspond to the subsequence $(b\_1, b\_4)$ of $b$.

[![enter image description here](https://i.sstatic.net/285H9.png)](https://i.sstatic.net/285H9.png)

The graph has a "row" for each sequence in the collection.
(In the example, the row for $a$ consists of the nodes 01-09 and 10-18.
The row for $b$ consists of the nodes 21-29 and 30-38.
The row for $c$ consists of the nodes 41-49 and 50-58.)

Consider any perfect matching of the graph.
Each row is composed of 4-cycles (e.g. $(01, 12, 02, 11)$) each with two "external" edges leaving the 4-cycle.
Because each 4-cycle has an even number of nodes, in any perfect matching, either both of the external edges (leaving the 4-cycle) are in the matching, or neither are. It follows that, within each row, either all the external edges are in the matching or none are. In the former case, each 4-cycle has two nodes matched by its two external edges, so the remaining two nodes must be matched (together) by the single zero-weight diagonal edge connecting them. (See the first row in Part (b) of the figure.) So, within the row, the matching is forced to use only zero-weight edges.

In the remaining case (in the row, none of the external edges are in the matching), within each 4-cycle, there are two matched edges --- either the two diagonal zero-weight edges, or the two vertical edges, whose weights are zero and one of the elements in the row's sequence. It follows that the weights of the matched edges in the row consist of any subsequence of the row's sequence, together with some zeros. (See the second row in Part (b) of the figure, in which there are matched edges for $b\_1$ and $b\_4$, together with some zero-weight edges.) In this way, the possible matched edges within the row correspond bijectively with the possible subsequences of the row's sequence.

Finally, because of the edges to the $L$ and $R$ nodes (each of which must have one matched edge), exactly one of the rows (the top row for $a$, the middle row for $b$, or the bottom row, for $c$) is in the "unforced" state, while the other two must be forced to use only zero edges.

In this way, we see the graph has the desired property:
for each subsequence $S$ of each sequence $a\in C$,
there is exactly one perfect matching in the graph whose non-zero edge weights are the weights in $S$
(and all perfect matchings in the graph can be obtained this way for some such $S$). Hence the reduction is correct. $~~\Box$

---

Next we describe a reduction from Unique-Weight Subset Sum (defined next) to USSC (as defined above).

**Definition 2.** Define *Unique-Weight Subset Sum* as follows. The input is a triple $(x, T, y)$ where $(x, T)$ is a standard Subset-Sum instance (so $x=(x\_1, x\_2, \ldots, x\_n)$ is a sequence of non-negative integers and $T$ is the target) and $y=(y\_1,\ldots, y\_n)$ is another sequence of non-negative integers. We call $x\_1, \ldots, x\_n$ the *primary weights* and $y\_1,\ldots, y\_n$ the *secondary* weights. The question is whether, among the subsequences of $x$ that sum to $T$, there is one such that the sum of the corresponding secondary weights is unique (among all subsets of $x$ that sum to $T$). Formally, among all index sets $S\subseteq \{1,2,\ldots,n\}$ such that $\sum\_{i\in S} x\_i = T$, is there one where $\sum\_{i\in S} y\_i$ is unique? (If there are no such subsequences summing to $T$, the answer is no.)

**Lemma 2.** *Unique-Weight Subset Sum reduces to USSC*.

*Proof.* Here is the reduction.
Fix an instance $(x, T, y)$ of Unique-Weight Subset Sum, with primary weights $x=(x\_1, x\_2, \ldots, x\_n)$, target $T$,
and secondary weights $y=(y\_1, \ldots, y\_n)$.
Assume without loss of generality that $T=2^k$ for some integer $k$ such that $\sum\_i x\_i < 2^{k+1}$. (Otherwise, for $k$ such that $\sum\_i x\_i < 2^k$, replace the target by $T'=2^{k}$ and add $x\_{n+1} = T'-T$ to the collection, with secondary weight $y\_{n+1}$ equal to zero. This preserves the instance because every subsequence that sums to $T'$ must include $x\_{n+1}$.)

The reduction outputs a USSC instance $C=(a, b, c)$ as defined below.
First, let $d$ be the number of bits needed to encode $\sum\_i y\_i$ in standard binary representation(so $\sum\_i y\_i < 2^d$).
Recall that $\sum\_i x\_i < 2^{k+1}$, so $k+1$ bits suffice to encode $\sum\_i x\_i$.
For each $i\in \{1,\ldots,n\}$,
take $a\_i$ to be the $(1+k+d)$-bit integer that encodes $y\_i$ in its $d$ least-significant bits,
while encoding $x\_i$ in its $k+1$ most-significant bits.
That is, take $a\_i = x\_i 2^d + y\_i$.

Then, for any $S\subseteq\{1,2,\ldots,n\}$, we have
$$\sum\_{i\in S} a\_i ~=~ 2^d \sum\_{i\in S} x\_i ~+~ \sum\_{i\in S} y\_i.$$
Further, $\sum\_{i\in S} y\_i$ is encoded in the $d$ least-significant bits of $\sum\_{i\in S} a\_i$,
while $\sum\_{i\in S} x\_i$ is encoded in the $k+1$ remaining (most-significant) bits of $\sum\_{i\in S} a\_i$.

Recall that the question is *among $S\subseteq\{1,2,\ldots,n\}$ such that the primary weights sum to the target ($\sum\_{i\in S} x\_i = T$), is there an $S$ such that the sum of the secondary weights ($\sum\_{i\in S} y\_i$) is unique?*

Given the previous considerations, and $T=2^k$,
the condition $\sum\_{i\in S} x\_i = T$ is equivalent to the condition that, if we encode $\sum\_{i\in S} a\_i$ as a $(1+k+d)$-bit integer,
the $(k+1)$ most-significant bits encode $T = 2^{k}$.

Thus, the question is equivalent to *among $S\subseteq \{1,\ldots,n\}$, is there one such that the sum $\sum\_{i\in S} a\_i$ is both unique (among all $S$), and its $k+1$ most-significant bits encode $2^k$?*

To capture the latter condition, we will construct $b$ such that the weights obtainable by summing subsequences of $b$ are exactly the $(1+k+d)$-bit integers whose $k+1$ most-significant bits do *not* encode $2^k$. And we will take $c=b$, so that all such weights can be obtained in at least two ways (and are therefore not candidates to be unique). Specifically, we take

$$b = c = (2^0, 2^1, \ldots, 2^{d+k-1}, 2^{k+d}+2^d).$$

Note the final weight has an extra additive $2^d$.
Using the weights in $b$ other than that one, one can make any sum in $\{0,1,\ldots,2^{k+d}-1\}$.
Then, by using the last weight in combination with some other weights in $b$,
one can make any sum in $\{2^{k+d}+2^d, \ldots, 2^{k+d+1}-1\}$.
So, one can make any $(1+k+d)$-bit integer except those in the range $\{2^{k+d}, \ldots, 2^{k+d}+2^d-1\}$,
that is, except those whose $k+1$ most-significant bits encode $2^k$, as desired.

It follows that there is a unique-weight subsequence of some sequence in $C=(a, b, c)$
if and only if the given Unique-Weight Subset Sum instance $(x, T, y)$ has a subsequence with total primary weight $T$ and unique total secondary weight. That is, the reduction is correct. $~~\Box$

---

To complete the proof of Theorem 1, we show that Unique-Weight SAT (as defined at the end of OP's post) reduces to Unique-Weight Subset Sum:

**Lemma 3.** *Unique-Weight SAT reduces to Unique-Weight Subset Sum.*

*Proof.* Fix an instance $(\phi(v), w)$ of Unique-Weight SAT. That is, $\phi$ is a Boolean formula on Boolean variables $v=(v\_1, v\_2, \ldots, v\_m)$, and $w=(w\_1, \ldots, w\_m)$ is a vector of non-negative integers, one for each variable. The question is whether there exists a satisfying assignment to $v$ such that the sum of the weights of the true variables is unique among all satisfying assignments.

The reduction is the standard reduction from SAT to Subset-Sum, augmented as follows. Let $(x, T)$ be the output of the standard reduction from SAT to Subset Sum, given input $\phi(v)$. Following that reduction, the satisfying assignments for $\phi$ correspond bijectively to subsequences of $x$ that sum to $T$. Further, for each Boolean variable $v\_i$ in $\phi$, there is a weight (WLOG $x\_i$) in $x$ such that, for each satisfying assignment to $v$ and its corresponding subsequence summing to $T$, $v\_i$ is true if and only if $x\_i$ is included in the subsequence. For each such variable $v\_i$, set $y\_i=w\_i$ (that is, the secondary weight of $x\_i$ is the weight of $v\_i$). Set the secondary weights of all remaining variables to zero.

This concludes the reduction. By inspection, the satisfying assignments for $\phi$ correspond bijectively with the subsequences of $x$ that sum to $T$, and the weight associated with each satisfying assignment equals the secondary weight associated with the corresponding subsequence of $x$. Thus, the reduction is correct. $~~\Box$

Lemmas 1-3 directly imply Theorem 1.

---

# Unique Permanent Term

Next we turn our attention to Unique Permanent Term (the problem defined at the top of OP's post).
The ideas are similar but work with products instead of sums.
First, in this section, we show the following theorem for *Unique-Product SAT* (the "product" variant of Unique-Weight SAT):

**Theorem 2.** *Unique-Product SAT (as defined below) reduces in polynomial time to Unique Permanent Term.*

(In the next section, to complete the answer, we sketch how to reduce Unique-Weight SAT to Unique-Product SAT.)

**Definition 3.** *Unique Product SAT* is the following problem: *Given a SAT formula having a positive integer weight associated with each variable, among satisfying assignments for the formula, is there one where the product of the weights of the true variables is unique?*

We prove Theorem 2 via a series of reductions, similar to the proof of Theorem 1.

We'll start by showing that the following technically convenient problem reduces to Unique Permanent Term:

**Definition 4.** Define *Unique Subset Product from Collection (USPC)* as follows.
The input is a collection $C$ of sequences of non-negative integers.
The question is whether there is a subsequence of any of the given sequences whose *product* is unique
(among all subsequences of all sequences $a\in C$).

**Lemma 4.** *There is a polynomial-time reduction from USPC to Unique Permanent Term.*

*Proof.* We note that Unique Permanent Term is equivalent to the following problem: *Given a bipartite graph $G=(U, W, E)$ with integer edge weights and $|U|=|W|$, is there a perfect matching such that the product of the weights of the matched edges is unique (among all perfect matchings)?* We reduce USPC to this problem.

The reduction and its proof are the exactly same as for the proof of Lemma 1 (reduction of USSC to Isolated Perfect Matching)
except that the unlabeled edges instead have weight 1 instead of zero,
and instead of considering sums of subsequences, we use products. $~~\Box$

---

Next we show that *Unique-Product 3D-Matching* (defined below) reduces to USPC.

**Definition 5.** *Unique-Product 3D-Matching* is the following problem:
*The input is a triple $(X, U, w)$ where $U$ is a universe of elements, $X$ is a collection of triples of elements in $U$,
and $w\_i$, a positive integer weight, is the weight associated with the $i$th triple.
The question is whether, among subsets $M$ of $X$ that partition $U$ (called 3D-matchings) there is one such that the product of the weights of the triples in $X$ is unique.*

**Lemma 5.** *There is a polynomial-time reduction from Unique-Product 3D-Matching to USPC.*

*Proof sketch.* The reduction is similar in spirit to [the classical reduction from standard 3D-Matching to the Subset Product problem](https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete).
Here is the reduction. Fix an input $(X, U, w)$ of Unique-Product 3D-Matching. Let $n=|U|$ be the size of the universe. Assume WLOG that $U=\{1,2,\ldots, n\}$.

Let $(x\_i, y\_i, z\_i)$ denote the $i$th triple, with (positive integer) weight $w\_i$. Call this weight the *primary* weight of the triple.

Let $p(1), p(2), \ldots, p(n)$ be the first $n$ primes that are relatively prime to every weight $\{w\_i\}$.
(That is, skip primes that are factors of some weight.
These primes can be found in time polynomial in $n$ e.g. using the Sieve of Eratosthenes or the AKS algorithm.)
Let $P=p(1)\cdot p(2)\cdot \cdots\cdot p(n)$ be their product.

Following the standard reduction from 3D-Matching to Subset Product,
associate with each triple $(x\_i, y\_i, z\_i)$ the product $p(x\_i)\cdot p(y\_i)\cdot p(z\_i)$. Call this product the *secondary weight* of the triple.

Then a subset $M\subseteq X$ of the triples forms a 3D-matching (i.e. partitions $U$)
if and only if the product of the secondary weights of its elements equals $P$.

Hence, the question is: *Among subsets of triples whose secondary weights have product $P$,
is there one for which the product of the associated primary weights is unique?*

We construct an instance $C$ of USPC that answers this question,
proceeding in a similar spirit as in the proof of Lemma 2.

The first sequence in the collection $C$ is $a$,
with an element $a\_i = w\_i\cdot p(x\_i)\cdot p(y\_i)\cdot p(z\_i)$ for each of the $m$ triples.

The question can now be stated as: *Among subsequences of $a$, is there one whose product is unique,
AND whose product includes each of the $n$ primes $p(1), p(2), \ldots, p(n)$ exactly once?*

To enforce the latter condition, for each of the $n$ primes $p(i)$,
we add *two* sequences to the collection $C$, each with exactly the following elements:

$$S(i)=\{w\_1, w\_2, \ldots, w\_m\} \cup \Big(\bigcup\_j \{p(j)^1, p(j)^2, \ldots, p(j)^m\}\Big) \setminus \{p(i)\}.$$

This completes the reduction.

Because we add *two* sequences with the elements in $S(i)$ to $C$,
none of the subsequences of any such sequence can have a unique product
(among subsequences of sequences in $C$).

And for any subsequence of $a$ that is missing one of the primes $p(i)$, or has two or more elements having a factor of $p(i)$,
the product of that subsequence is the same as the product of some subsequence of $S(i)$,
so its product is not unique. Conversely, if a subsequence of $a$ has, for each $p(i)$, exactly *one* element having $p(i)$ as a factor,
then that subsequence's product has just one factor of each $p(i)$, so the product is not the same as the product of any subsequence of any $S(i)$.

It follows that there is a unique-product subsequence of one of the sequences in $C$
if and only if, among 3D-matchings of the given graph, there is one whose product of weights is unique. $~~\Box$

---

Finally we reduce *Unique-Product SAT* (defined above, Definition 3) to Unique-Product 3D-Matching.

**Lemma 6.** *There is a polynomial-time reduction from Unique-Product SAT to Unique-Product 3D-Matching.*

*Proof sketch.* The reduction is the standard (parsimonious) reduction from SAT to the standard 3D Matching problem, modified as follows. That reduction produces a 3D-matching instance $(X, U)$ whose 3D matchings correspond bijectively to the satisfying assignments of the given formula. Furthermore, for each variable of the given SAT formula, there is a triple in $X$ such that, in any satisfying assignment, the variable is true if and only if that triple is in the 3D matching. For each variable, choose such a triple and give it weight equal to the weight of its variable. Give all other triples weight 1. Then the product of the weights for any satisfying assignment equals the product of the weights for the corresponding 3D matching. This implies that the reduction is correct. $~~\Box$

Theorem 2 follows directly from Lemmas 4--6.

---

# All these problems are complete for UW-NP

To finish we sketch how Unique-Weight SAT is equivalent to Unique-Product SAT (under poly-time reductions).

To do this, recall the complexity class UW-NP defined at the start of the answer.
(It contains languages definable as follows: given any poly-time non-deterministic Turing Machine $M$, its language $L(M)$ is the set of inputs $x$ to $M$ such that, among all non-deterministic executions of $M$ on input $x$, there is at least one whose output is unique, where the output is the contents of the tape when the execution halts.)

Unique-Weight SAT and Unique-Product SAT are clearly in UW-NP.
To show that they are equivalent, we show the following lemma:

**Lemma 7.** *Unique-Weight SAT and Unique-Product SAT are each UW-NP-complete (under poly-time reductions).*

*Proof sketch.* First we argue that Unique-Weight SAT is UW-NP-complete.

The basic idea is to modify the standard proof that SAT is NP-complete, by adding weights to the variables of the SAT formula. In particular, in the standard proof, the SAT formula has, for each tape cell $i$, tape symbol $\tau$ in the tape alphabet $\mathcal{T}$, and time $t$, a Boolean variable $v(i, \tau, t)$ that encodes whether tape cell $i$ contains $\tau$ at time $t$. If time $t$ is not the termination time, we give this variable weight zero. Otherwise we give it weight $(j-1)|\mathcal{T}|^i$, where $\tau$ is the $j$th tape symbol in $\mathcal{T}$.
This completes the reduction.

Then the non-deterministic execution paths correspond bijectively with the satisfying assignments to the formula,
and the total weight of each satisfying assignment faithfully encodes the output, so the reduction is correct.

(I am waving my hands here a bit -- e.g. in the assumption that all execution paths end at the same time.
I believe such technical details are addressable but getting into them would take us too far afield.)

The proof for Unique-Product SAT is the same except for the assignments of weights to variables.
For Boolean variable $v(i, \tau, t)$, if time $t$ is not the termination time, give the variable weight 1.
Otherwise, give the variable weight $p\_i^j$, where $p\_i$ is the $i$th prime and $\tau$ is the $j$th symbol in the tape alphabet.
(Note that the first $n$ primes [can be calculated and encoded in time poly$(n)$](https://cs.stackexchange.com/questions/7907/is-the-subset-product-problem-np-complete).)
Then the non-deterministic execution paths correspond bijectively with the satisfying assignments to the formula,
and the product of the weights of each satisfying assignment faithfully encodes the output, as desired.
$~~\Box$

---

By Lemmas 1--7, all of the problems mentioned in this answer are UW-NP-complete, and therefore equivalent under poly-time reductions. This (barring mistakes) answers the posed question. (Well, we didn't consider Unique-Weight Hamiltonian Cycle, but it is clearly in UW-NP and can easily be shown UW-NP complete by reduction from Unique-Weight SAT, by adapting the standard reduction from SAT to Hamiltonian Cycle.)

---

# Concluding remarks and questions

Some observations about how UW-NP relates to existing complexity classes:

**Observation 1.** *UW-NP contains NP.*

(For Unique-Weight SAT, the special case when all weights are distinct powers of two is equivalent to regular SAT, because every assignment has a distinct total weight.)

**Observation 2.** *UW-NP contains the complexity class [US](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#us).*

(US contains languages defined as follows: given any non-deterministic poly-time TM, its language contains the inputs for which exactly one execution path accepts. The restriction of Unique-Weight SAT to instances where all weights are zero is equivalent to the classical [Unique SAT problem](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT) (*"Given a Boolean formula, does it have exactly one satisfying assignment?"* --- not to be confused with *[Unambiguous SAT](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT)*, which is the promise problem obtained by restricting SAT to instances where there is at most one satisfying assignment).
Unique SAT (and, via parsimonious reductions, Unique Hamiltonian Cycle) are complete for the complexity class [US](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#us).

US also contains co-NP (and is contained in [DP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp)). US is considered unlikely to be equal to co-NP [e.g. [here](https://doi.org/10.1007/3-540-48321-7_27), [here](https://doi.org/10.1016/S0019-9958(82)90439-9)]. So:

**Observation 3.** *UW-NP contains co-NP.*

Is UW-NP contained in [DP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp)? It is contained in $\Sigma\_2$P; is it equal to $\Sigma\_2$P?

---

What about the problems below?

1. *Given an edge-weighted digraph, does it have a simple $s$-$t$ path whose weight is unique?* This seems to be UW-NP-complete (e.g. by reduction from Unique-Weight Hamiltonian Cycle). The corresponding counting problem (*Given a digraph, how many simple $s$-$t$ paths does it have?*) [is #P-complete](https://doi.org/10.1137/0208032).
2. *Given an edge-weighted graph, does it have a spanning tree whose weight is unique?* Is this one UW-NP-complete? The corresponding counting problem (*Given a graph, how many spanning trees does it have?*) is in P.
3. For all of these problems, instead of asking whether there exists at least one unique-weight object, we could ask whether there exist at least two objects that have the same weight. These variants are generally in NP, and NP-hard if the underlying search problem is NP-hard (by taking the weights to be zero, essentially). But what about problems where the underlying search problem is in P, e.g., *Given an edge-weighted bipartite graph, are there two perfect matchings with the same weight*?

---

> **Comments:**
> **username_0**: I think this has outgrown the size of a cstheory.SE answer...  
> **username_4**: I agree it is rather long. The result for Isolated Perfect Matching is short enough, or the reduction from Unique-Product SAT to Unique Permanent Term would be, but I don't see any shorter way of getting from Unique-Weight SAT to any "unique product" problem  
> **username_2**: Uh, yeah, this seems to me like a paper. You should publish it! (Or maybe see if username_0 wants to combine it with whatever led to this question and publish together...)  
> **username_2**: Re: your question about being in DP. It's not even clear to me that it is in [BH](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bh). The issue is that, for the Boolean hierarchy over NP, the languages you are taking Boolean combinations of don't "know about" each other's witnesses, so it seems hard to detect unique outputs in this way. I wonder if it is related to [HNOS](https://doi.org/10.1137/S0097539794268315).  

---

### Answer by username_3 on 2010-10-10. Score: 14

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...

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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.  
> **username_4**: The reduction to ISOLATED PERFECT MATCHING, as described above, isn't necessarily polynomial time.  Using standard encodings, it increases the encoding sizes of the weights exponentially.  

---

