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

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

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

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