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


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

# I will create a function to shuffle B later

def shuff(B, n):
    for i in range(n-1,0,-1):
        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

    if length(Potential_solution) == length(ss)//3:
        # break if Exact
        # three cover is
        # found.
        OUTPUT YES
        failed_lists = failed_lists + 1

    # 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.
    del [B[0]]
    Potential_solution = []
    s = set()
    for l in B:
        if not any(v in s for v in 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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.