# Would this algorithm fail to count solutions $>$ $1$ for Exact-3-cover?

Decision Problem: Given a set $$S$$, is there at least a given $$N$$ $$>$$ $$1$$ amount of solutions, for an $$Exact~Cover~by~3-sets$$ for $$C%$$?

$$s$$ = $$1,2,3,4,5,6$$

$$c$$ = $$[[1,2,3],[4,3,2],[4,5,6],[5,1,6],[5,6,3]]$$

## Solutions

$$[1,2,3],[4,5,6]$$

$$[4,3,2],[5,1,6]$$

$$N$$ = $$2$$

Yes, there are $$N$$ solutions.

## Algorithm

1. Remove sets that have repeating elements

(eg. [1,1,2] is deleted from $$C$$)

2. Remove sets that have elements that don't exist in $$S$$

(eg. [9,5,6] is deleted because $$9$$ not in $$S$$)

3. Make sure all elements in $$S$$ exist in $$C$$.

$$for$$ a $$in$$ $$range(0, length(s)):$$

$$~~~~~~~~IF$$ $$s[a]$$ $$not$$ in $$c$$:

$$~~~~~~~~~~~~~$$OUTPUT NO

## Convert $$C$$ into a complete list

$$WHILE$$ $$c[i]$$ has [brackets]:

$$~~~~~~~~~~$$ DELETE [BRACKETS] FROM $$C$$

now $$c$$ = $$[1, 2, 3, 4, 3, 2, 4, 5, 6, 5, 1, 6, 5, 6, 3]$$

## Finally, Decide

$$n$$ = $$('Enter~for~N:~'))$$

$$yes$$ = $$0$$

$$for$$ a $$in$$ $$range$$(0, $$length(c)):$$

$$~~~~~~if$$ $$c$$.count($$c$$[a]) >= $$n$$ :

$$~~~~~~~~~~yes$$ = $$1$$

$$~~~~~~$$else:

$$~~~~~~~~~~$$OUTPUT NO

$$~~~~~~~~~~$$HALT

$$if$$ $$yes$$ == $$1$$ :

$$~~~~$$OUTPUT YES

Edit: The above should do the same below.

yes = 0
for a in range(0, length(s)):
if c.count(s[a]) >= n:
yes = 1
else:
OUTPUT('No')
break

if yes == 1:
OUTPUT('yes')


## Facts to consider

1. There cannot be any sets with elements that don't exist in $$S$$.

2. There cannot be any sets with repeating elements.

3. All elements in $$S$$ must exist in $$C$$. Else, a $$no$$ is given.
4. $$N$$ must be > $$1$$
5. If any element in $$C$$ occurs < $$N$$ times then the output must be $$No$$, because there wouldn't be at least $$N$$ solutions.

Question

Will this algorithm always work if the input is > $$1$$, and if no how would it fail?

• If it fails, I will resort to using the counting method for $S$ and compare it to the number of times $S[a]$ occurs in $C$. – Dingle Berry May 30 at 22:39
• $S = \{1, ..., 9\}$. $C = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [4, 8, 9], [5, 6, 7]]$ $N=2$ – Vladislav Bezhentsev May 30 at 23:03
• [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and [[1, 2, 3], [4, 8, 9], [5, 6, 7]] Why these solutions are bad? – Vladislav Bezhentsev May 30 at 23:10
• I ran it on input that we have discussed above. Do you agree that this input has at least two solutions? – Vladislav Bezhentsev May 30 at 23:26
• What are you trying to do? It's HIGHLY unlikely that you will be able to find a poly-time algorithm for an NP-complete problem. – Vladislav Bezhentsev May 31 at 21:52