0
$\begingroup$

Suppose, 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 $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$ 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 primes raised to 6.

A collection of subsets would be represented as {$p_1^6, p_2^6, p_3^6$}, {$p_4^6,p_5^6,p_6^6$}....

Update: If 2 becomes an issue, we can just use the first N distinct odd primes instead.

Update: Does the unique factorization of $p_i^6$ also imply that $S$ has a unique sum thus preventing collisions? I've exhaustively tried combinations allowing repeated usage from $S$ to simulate collisions. I wanted to see if it were possible to get a sum to $S$ with repeated usage. Didn't find a counter-example this way either. If brute force won't practically find a counter-example, then we need to figure out something more clever. Perhaps this link to mathoverflow might help in constructing a counter example.

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

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.

Here's a link to my code for empirical analysis showing no duplicate sums

Let's say that conjecture is true, what about the sum of the transformed $S$? I asked this because we will be using the Subset Sum dynamic solution to solve Exact 3 Cover. Since there's no duplicate sums per the conjecture, then there should be no collisions resulting a false output when we use the Subset Sum algorithm.

The magnitude of the sum of the transformed S.

Let's denote the $i-th$ prime number as $p_i$ where $i = 1,2,....len(S)$. The sum of the transformed $S$ can be represented as $\sum_{i=1}^{len(S)} p_i^6$

Now to prove that the sum is polynomial, we need to show that the largest term in the sum grows polynomially with respect to $len(S)$.

If my understanding is correct (and I could be wrong) the $i-th$ prime number, $p_i$ is approximately $i*log(i)$ according to the prime number theorem.

Therefore, $p_i^6$ can be approximated as $(i*log(i))^6$.

Expanding the expression, I get:

$(i*log(i))^6 = i^6 * (log(i))^6$

Both $i^6$ and $(log(i)^6$ are polynomial functions. Therefore, the sum $\sum_{i=1}^{len(S)} p_i^6$ is a sum of polynomial terms, making it polynomial.

But if my understanding is correct seems to show that the magnitude of the sum of the transformed $S$ is polynomial in the size of $S$.

If we use the subset sum dynamic solution which is pseudo polynomial, it would be polynomial in the transformed size of $S$.

Has this conjecture already been shown to imply $P=NP$, or has it been debunked?

Where's the counter-example?

$\endgroup$
5
  • 2
    $\begingroup$ It is unclear (to me) how the proposed reduction from X3C to Subset Sum works. For example, given the simple (Yes) instance of X3C $S=\{1,2,3,4,5,6\}$ $C = \{\{1,2,3\},\{4,5,6\},\{2,3,4\}\}$; what are the numbers associated with each subset in $C$ and what is the total target sum wanted? $\endgroup$ Apr 11 at 13:13
  • 1
    $\begingroup$ ... ok, now I got it: the target sum is $\sum_{i=1}^{|S|} p_i^6$; each subset $\{a_i, a_j, a_k\}$ in $C$ is represented simply with $p_i^6 + p_j^6 + p_k^6$ (and the reduction is polynomial-time). $\endgroup$ Apr 11 at 16:20
  • $\begingroup$ @MarzioDeBiasi I tried writing my reduction in python code, as I see you're programmer. If I don't have any bugs I hope this helps. Forgive me if the code is to long. pastebin.com/RxKViyXa Edit: I forgot to output the target sum, but its defined as N in the code. $\endgroup$
    – The T
    Apr 11 at 17:19
  • $\begingroup$ @MarzioDeBiasi In the linked pastebin get_the_sums should've been this pastebin.com/LivhbgEV . We need to see if duplicate sums are possible. $\endgroup$
    – The T
    Apr 11 at 18:01
  • $\begingroup$ mathoverflow.net/q/468737/37212, math.stackexchange.com/q/4894190/14578 $\endgroup$
    – D.W.
    Apr 12 at 6:56

1 Answer 1

2
$\begingroup$

I think that you cannot guarantee an unique sum, but the numbers for a counterexample must be taken at "the end of the universe".

You can find primes $p_{i_j}$ and factors $k_j$ such that $\sum_{j=1}^N k_j p_{i_j}^6 = p_{i_{N+1}}^6$.

For example: $8^6 + 12^6 + 30^6 + 78^6 + 102^6 + 138^6 + 165^6 + 246^6 = 251^6$

we can "extract" a distinct prime from each one of the 6-th powers:

$8^6 = 4096 * 2^6,\;$ $12^6 = 4096 * 3^6,\;$ $30^6 = 46656 * 5^6,\;$ $78^6 = 46656 * 13^6,\;$ $102^6 = 17 46656 * 17^6,\;$ $138^6 = 46656 * 23^6,\;$ $165^6 = 11390625 * 11^6,\;$ $246^6 = 46656 * 41^6 $

so if you have $4096+1$ 3 elements subsets that contains a common $2^6$ (and the others are all distinct "new elements"), $4096+1$ 3 elements subsets that contains a common $3^6$ (and the others are all ditinct "new elements"), and so on ...

You get a collection of (overlapping) sets that represents the elements $2^6 , 3^6 , 5^6 , 13^6 , 17^6, 23^6, 11^6, 41^6$ and the "new" $251^6$, plus a very large set of unique (and non-overlapping) elements.

If the element $251^6$ is not included in any of the 3 element subsets (or included in a forced invalid overlapping chain of primes) you get a VALID YES INSTANCE of the Subeset Sum from a NO INSTANCE of the original 3XC problem.

$\endgroup$
7
  • $\begingroup$ You actually went through it and gave an example. Nice ! $\endgroup$
    – Tayfun Pay
    Apr 12 at 1:02
  • 1
    $\begingroup$ Its been a hurtin' for me. I'm impressed. Of course I will continue my research into seeing what larger exponents would do. $\endgroup$
    – The T
    Apr 12 at 1:04
  • $\begingroup$ Just curious how large was S and C? $\endgroup$
    – The T
    Apr 12 at 1:19
  • $\begingroup$ @TheT: $S$ contains at least 2*(4097+4097+46657+46657+1746657 +46657+11390627+46657)+8 distinct elements (each one mapped to a $p_i^6$) in order to build enough 3 element subsets that sum up to 251^6; plus a bunch of other elements to fill the gaps and make the total count divisible by 3 (7^6,19^6, 27^6, ..., 241^6, 251^6, 257^6) ... something like N=13230648 elements . $\endgroup$ Apr 12 at 7:12
  • 1
    $\begingroup$ @TheT: I think it's hard to find a smaller counterexample (I just looked at the KNOWN 6-th power diophantine equations, and it is very small). And be aware to play with larger exponents, because number-theory is full of UNKNOWN/UNPROVED stuff even for "smaller" objects so you risk getting nowhere. Even for your actual question, it is unknown if you can represent a 3-element subset uniquely with the sum of 3 6-th prime powers without any collision (so even if there had been no counterexample to the entire reduction, you would have been stuck) $\endgroup$ Apr 12 at 12:38

Your Answer

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

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