I devote my questions on this site to learn and expand my research into finding Polynomial Time Randomized Heuristic Algorithms for Exact 3 Cover. This is a hobby of mine, my goal is to look for the most efficient algorithms possible for Exact 3 Cover.

Anyway, if anyone is interested here's the details.

Suppose, I'm solving X3C, 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 X3C into SSUM by transforming $S$ into randomly assigned $N$ distinct odd primes raised to random exponents either $5,6,7$ 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.

I generate a list of the first $N * 10$ distinct odd primes. This is where I get my $N $distinct random primes. Generating these takes polynomial time per the prime number theorem because $i * log(i)$

Or in this case the time complexity would be approximately $i * log(i) * 10$

So now I have a transformed $S = {p_1^6, p_2^5, p_3^5...} $into the $N$ distinct primes raised to a random exponent of either $5, 6 or 7$ .

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

Now, my heuristic uses the dynamic solution for subset sum it is true polynomial time.

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

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

The $i-th$ prime number, $p_i$ is approximately $i*log(i)$ according to the prime number theorem.

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

Expanding the expression, I get: $(i*log(i))^c = i^c * (log(i))^c$

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

This shows that the magnitude of the sum of the transformed $S$ is polynomial in the size of S. Thus my heuristic is polynomial time. Albeit extremely impractical.

Finding counter-examples are just as hard as this problem.

If we find a Diophantine equation that sums up to the universe $S$, and there's duplicate positive integers then the reduction failed, because that would be a collision.

The algorithm is way to long to paste here, so here’s a pastebin.