19
$\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 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?

$\endgroup$
2
  • 1
    $\begingroup$ Do we know if this problem is even in NP? I'm having difficulty coming up with a certificate. $\endgroup$
    – mhum
    Oct 14, 2010 at 1:01
  • 1
    $\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$ Oct 14, 2010 at 1:06

2 Answers 2

7
$\begingroup$

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 Scott Aaronson'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 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

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

(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 ("Given a Boolean formula, does it have exactly one satisfying assignment?" --- not to be confused with Unambiguous 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.

US also contains co-NP (and is contained in DP). US is considered unlikely to be equal to co-NP [e.g. here, here]. So:

Observation 3. UW-NP contains co-NP.

Is UW-NP contained in 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.

  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?


$\endgroup$
4
  • $\begingroup$ I think this has outgrown the size of a cstheory.SE answer... $\endgroup$
    – domotorp
    Feb 13, 2020 at 19:52
  • $\begingroup$ 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 $\endgroup$
    – Neal Young
    Feb 14, 2020 at 2:56
  • $\begingroup$ 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...) $\endgroup$ Feb 24, 2020 at 7:04
  • 1
    $\begingroup$ Re: your question about being in DP. It's not even clear to me that it is in 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. $\endgroup$ Feb 24, 2020 at 7:13
14
$\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$
3
  • $\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, 2010 at 6:16
  • 9
    $\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$ Oct 10, 2010 at 20:05
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Feb 3, 2020 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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