# Greedy Probabilistic Algorithm for Exact Three Cover I have a probabilistic greedy algorithm for Exact Three Cover. I doubt it’ll work on all inputs in polytime. Because the algorithm does not run $$2^n$$ time. I will assume that it works for some but not all inputs.

Our inputs are $$S$$ and $$B$$

$$S$$ is just a set of integers

$$B$$ is a list of 3-element {}s

## Algorithm

1. Input validation functions are used to ensure that sets of 3 are $$elements$$$$S$$.

2. A simple $$if~~statement$$ makes sure that $$|S|$$ % $$3$$ = $$0$$

3. I treat the sets like lists in my algorithm. So, I will sort all my sets from smallest to largest magnitudes (eg {3,2,1} now will be sorted to {1,2,3}

4. I will also sort my list of sets called $$B$$ in an ordering where I can find all {1,2,x}s with all other {1,2,x}s. (eg, sorted list {1,2,3},{1,2,4},{4,5,6},{4,5,9},{7,6,5} )

5. I will also genereate a new list of sets containing elements where a {1,2,x} only occurs one time in $$B$$.

6. Use brute force on small inputs and on both sides of the list $$B$$ up to $$|S|$$ / $$3$$ * $$2$$ sets. (eg. use brute force to check for exact covers on left and right side of the list `B[0:length(s)//3*2]` and reversed `B[0:length(s)//3*2]`)

## Seed the PRNG with a Quantum Random Number Generator

``for a in range(0, length(B)):     o = quantumrandom.randint(0, length(B))     random.seed(int(o))  # I will create a function to shuffle B later  def shuff(B, n):     for i in range(n-1,0,-1):         random.seed()         j = random.randint(0,i+1)         B[i],B[j] = B[j],B[i] ``

## Define the number of times while loop will run

``n = length(s)  # This is a large constant. No instances # are impractical to solve.  while_loop_steps = n*241*((n*241)-1)*((n*241)-2)//6 ``

## While loop

``stop = 0 Potential_solution = [] opps = 0 failed_lists = 0 ss = s  while stop <= while_loop_steps:      opps = opps + 1     stop = stop + 1      shuff(B,length(B))          if length(Potential_solution) == length(ss)//3:         # break if Exact         # three cover is         # found.         OUTPUT YES         failed_lists = failed_lists + 1         HALT      # opps helps     # me see     # if I miss a correct     # list           if opps > length(B):         if failed_lists < 1:             s = set()             opps = 0               # Keep B     # and append to     # end of list     # del B     # to push >>     # in list.       B.append(B)     del [B]     Potential_solution = []     s = set()          for l in B:         if not any(v in s for v in l):             Potential_solution.append(l)             s.update(l) ``

Run a second while loop for new_list if Step 5 meets the condition of there being only ONE {1,2,x}s )eg. {7,6,5} shown in step 4

## Two Questions

How expensive would my algorithm be as an approximation for Three Cover?

And, what is the probability that my algorithm fails to find an Exact Three Cover when one exists? Posted on Categories proxies