Share Your Experience: Take the 2024 Developer Survey
The T
• Member for 5 years, 1 month
• Last seen more than a week ago
• USA
Stats
159
reputation
489
reached
0
2
questions
Communities
View all

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.

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.

This user doesn’t have any gold badges yet.
This user doesn’t have any silver badges yet.
7
Top tags
0
Score
1
Posts
50
Posts %
0
Score
1
Posts
50
Posts %
0
Score
1
Posts
50
Posts %
0
Score
1
Posts
50
Posts %
Top posts
4
Sep 1, 2020
Top network posts
View all network posts