# 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 generate 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[0]
# and append to
# end of list
# del B[0]
# to push >>
# in list.

B.append(B[0])
del [B[0]]
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?

• Repeating sets can trivially be removed if they affect the probablity negatively. Jul 12, 2020 at 18:55