1

Consider I have $S$ elements $1,\ldots,3000$.

And $30,000$ $3-sets$ in $C$.

(eg.$C = [[1,2,3],[4,5,6]\ldots]] 29,998 \text{ more to go}$)

This I find really strange. A solution has $\operatorname{length}S/3$ units. Our solution must have $1000$ 3-element units from $C$.

$1000/30,000$ odds is $1/30$ odds.

Since Exact Three Cover is NP-complete it isn't expected to take $1/\operatorname{length}(C)$ odds to find a solution assuming one exists. (That would be a very practical probabilistic algorithm)

Question

If my math is correct, that there are an essential $1/30$ odds of randomly selecting a correct solution, then why does it still take exponential time?

Is my math wrong?

Michael Hardy
  • 1
Dingle Berry
  • 35

1 Answers1

2

You would be right if there were only 30 ways to choose 1,000 sets of 3 out of 30,000 items. But the real number of possible choices is computed by this formula

$$ \dfrac{n!}{(n-r)!} $$

where $n$ is 30,000 and $r$ is 1,000. That is 30,000 times 29,999 times 29,998 times ... times 29,001. I don't know the exact value of this number, but it can't be any smaller than $29,000^{1000}$ and that number has over 4500 digits. So the probability of guessing a correct solution is nowhere near 1/30.

A refresher on permutations and combinations is probably in order.

Kyle Jones
  • 1,871
  • Why would you use units more than one time for a polynomially sized solution? Lol There isn't n! solutions due to the pigeonhole principle. – Dingle Berry Jun 18 '20 at 02:07
  • As a kinf of comparison, if you had to guess a 4 digit PIN, would you say the odds are $\frac1{40}$ because you have 10 guesses for each digit and 4 guesses? In your example, as Kyle Jones wrote, you have a biiiiiig number of possible choices. Just because you only need to pick $\frac1{30}$ of your sets doesn't mean any thirty's pick is a solution on average. – Ingix Jun 18 '20 at 08:37
  • @Ingix Doesn't mean I have to use 4! possible ways to find that out. I'll look for the most common places your fingerprints would be on your keyboard. That will help narrow down the number of possibilities. I look for patterns. Now, I do believe that a non-exponential algorithm exists on some non-classical architecture that would solve NP-complete problems. It would have to be a genius to make such a non-classical computer practical!! – Dingle Berry Jun 19 '20 at 01:00
  • Can the brute force search of all those selection in your 3-cover problem be narrowed down from the number Kyle Jones gave? Almost certainly. Can it be narrowed down to something that even approaches your 1:30 odds? Almost certainly not, in the general case Are your 1:30 odds based on anything even remotely relevant to the problem: Not at all, IMO. That's what this answer points out. – Ingix Jun 19 '20 at 07:33