Could I possibly exploit distinct odd primes raised to 6 to solve Exact Three Cover, when reducing it in Subset Sum?

Question

I'm solving Exact 3 Cover, given a list with no duplicates $S$ of $3m$ whole numbers and a collection $C$ of subsets of $S$, each containing exactly three elements. The goal is to decide if there are $\operatorname{len}(S)/3$ subsets that cover every element in $S$ one time.

$N$ is the $len(S)$

I'm going to use Subset Sum to solve Exact 3 Cover.

I reduce Exact Three Cover into Subset Sum by transforming $S$ into $N$ odd distinct primes raised to 6, and easily map out the collection of subsets in the same manner. I then get the sums of the transformed collection of subsets. And the sum of the transformed $S$ will be our target sum.

So now I have a transformed $S = {p_1^6, p_2^6, p_3^6...}$ into the first $N$ distinct odd primes raised to 6.

There are rules for combinations of size three to ensure distinctness.

• All combinations of size three must be sorted in ascending order.
• There will be no duplicate subsets.
• There will be no subsets that have elements not in S .
• There will be no subsets that have duplicate elements.
• This does not affect correctness, as it is either impossible or not necessary that a solution could use these subsets. We easily filter the input to get rid of these unnecessary subsets.

The conjecture is that no distinct subset that was transformed into primes raised to 6 could have duplicate sums. Because duplicates could cause collision and the reduction would fail. This is a variant of the unsolved problem of $a^6 + b^6 + c^6 ≠ d^6 + e^6 + f^6$ where variables are distinct primes.

In this case both sides of the equation is supposed to be distinct subsets of size three. Of course, we have to tweak it to encapsulate all combinations of size 3.

For example,

When a variable is shared between two distinct subsets.

$A^6 + b^6 + c^6 ≠ A^6 + e^6 + f^6$

$b^6 + c^6 ≠ e^6 + f^6$ is another open problem for distinct primes, it also implies $A^6 + b^6 + c^6 ≠ A^6 + e^6 + f^6$

When two variables are shared between two distinct subsets.

$A^6 + B^6 + c^6 ≠ A^6 + B^6 + f^6$.

What about when two subsets share all variables?

• Per the rules of combinations no duplicate subsets. Because $a^6 + b^6 + c^6 = a^6 + b^6 + c^6$

For generality the position of shared variables could be at any location on either side of the equation.

Also the unique factorization of each $p^6$ seems to imply unique sums for all combinations of size 3.

My question is, could I possibly exploit properties of numbers to solve Exact Three Cover more efficiently?

Everybody's looking to use conventional techniques to solve NP complete problems, but nobody seems to looking for how numbers work. And, I think that could yield interesting finds. Even if the reduction is dependent on conjecture, its still nonetheless interesting.

I have written code for empirical analysis, and I've had no duplicate sums all the way up to 500.

This was originally asked on Theoretical Computer Science

Answer 1

Going by your notation, $c \in C$, $c=(x_1, x_2, x_3), x_i \in S \simeq \{1, \cdots , N \}$, and $\phi(c) \to \mathbb N$ the map you mentioned, $(\alpha_1,\cdots, \alpha_3) \mapsto \sum_i p_{\alpha_i}^6$.

Suppose $x \in S$ and $x \in c$, and $x \in c'$ for distinct $c \neq c' \in C$. Then $\phi(c) - \phi(c')$ would indeed involve a canceled $p^6$ term and be left with the sum of two sixth powers minus the sum of two sixth power primes. So this is the weakest case you can't include in a solution to your exact 3 cover.

Instead, you want them to be of the form of sums of three powers of six minus sums of three powers of six. Alright, so how do we put subset sum in the mix? Any solution to subset sum involving the entire set $S^*=\{\phi(c), c\in C\}$ will be dual to partitioning $S^*$ into two sets whose difference of sums is minimal. It is not obvious to me how such a partition would help us to solve this issue of distinguishing $a^6+b^6-c^6-d^6$ from $a^6+b^6+c^6 - d^6-e^6-f^6$, even if you expand the set to $S^{*2}$, a partition, or subset sum doesn't appear to elucidate the structure you're looking for.

The partitioning of the sums of powers of six, even if unique, does not appear to help in this way. Perhaps there is another clever way to set up the set we are taking subset sum or partitions of. But the core issue here is that you have to both balance the incidence of the $c_i$ pairings to never intersect, as well as make sure that every $x \in \sum_i c_i=^? S$ Doesn't seem obvious how to encode variables in such a way that sums of those to zero or a partitioning of those into minimal differences could somehow encode simply with a dot product and weight construction the balancing operation that is required for this. I'd be happy if I am proven wrong but I simply don't see it yet!