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

EditorJul 22, 2020

StudentJul 22, 2020

AutobiographerMay 8, 2019