What's wrong with this clique math?
April 10, 2023 2:38 AM Subscribe
I was watching this video about P = NP problems and it described the clique problem. I had a thought about one way to solve the clique problem - though of course with very little math knowledge I'm very aware that I have not Solved Math and likely am overlooking something major (the Wiki article went past my head). What's the matter with my possible algorithm?
Here's the algorithm, which assumes all pairs are bidirectional and nobody changes connections while you're calculating this.
1. Take your group of people as well as your desired clique size. For the purposes of this demonstration, let's assume you havea group of 6 - Alice, Bob, Charlie, Daniel, Emily, Frank - and you want a clique of 3.
2. List out each possible set of 3, and break those into each possible pair.
a) Alice, Bob, Charlie: (Alice + Bob) (Bob + Charlie) (Alice + Charlie)
b) Alice, Bob, Daniel: (Alice + Bob) (Bob + Daniel) (Alice + Daniel)
[etc etc etc]
z) Daniel, Emily, Frank: (Daniel + Emily) (Daniel + Frank) (Emily + Frank)
3. Check your group for one possible pair. For instance, let's start with Alice and Bob. We see that they are friends.
4. For each set that has the pair you just checked, give it 1 point. In our example list, (a) and (b) (and a bunch in the "etc etc" list) would get 1 point each.
5. Check another pair. If they are not friends, such as Bob + Charlie, don't add any points to the sets - just move on to the next pair. Do this for all possible pairs.
6. Once you've done this with all possible pairs, refer back to the list and rank them by how many points they get. Any group with 3 points would fit your required clique.
I'm imagining that the issue with this is that cross-referencing multiple lists of people (the group itself, each possible set, each possible pair, each possible pair in a set) would get unwieldly fast. Is this already a method outline in the Wiki article about the clique problem? What other issue exists with my algorithm?
(Assume high school knowledge of math, so maybe Explain Like I'm 16 or something)
Here's the algorithm, which assumes all pairs are bidirectional and nobody changes connections while you're calculating this.
1. Take your group of people as well as your desired clique size. For the purposes of this demonstration, let's assume you havea group of 6 - Alice, Bob, Charlie, Daniel, Emily, Frank - and you want a clique of 3.
2. List out each possible set of 3, and break those into each possible pair.
a) Alice, Bob, Charlie: (Alice + Bob) (Bob + Charlie) (Alice + Charlie)
b) Alice, Bob, Daniel: (Alice + Bob) (Bob + Daniel) (Alice + Daniel)
[etc etc etc]
z) Daniel, Emily, Frank: (Daniel + Emily) (Daniel + Frank) (Emily + Frank)
3. Check your group for one possible pair. For instance, let's start with Alice and Bob. We see that they are friends.
4. For each set that has the pair you just checked, give it 1 point. In our example list, (a) and (b) (and a bunch in the "etc etc" list) would get 1 point each.
5. Check another pair. If they are not friends, such as Bob + Charlie, don't add any points to the sets - just move on to the next pair. Do this for all possible pairs.
6. Once you've done this with all possible pairs, refer back to the list and rank them by how many points they get. Any group with 3 points would fit your required clique.
I'm imagining that the issue with this is that cross-referencing multiple lists of people (the group itself, each possible set, each possible pair, each possible pair in a set) would get unwieldly fast. Is this already a method outline in the Wiki article about the clique problem? What other issue exists with my algorithm?
(Assume high school knowledge of math, so maybe Explain Like I'm 16 or something)
Best answer: You note that your algorithm would "get unwieldy fast". Basically, the P vs NP classification tells you how fast a problem gets unwieldy as you apply it to bigger and bigger situations. A P problem gets unwieldy in a "manageable" way; but an NP problem gets unwieldy so fast that for all practical purposes it's unsolvable beyond a certain size.*
The algorithm you're describing is basically a "brute force algorithm" of the kind described in the caption of the picture at the top of the Wikipedia page, and also mentioned in the subsection "Cliques of fixed size". (And in the video, for that matter — you've just filled in some of the details of the boxes in the flowchart she shows around 4:10.) For a fixed clique size, this algorithm actually does run in polynomial time (i.e., it gets unwieldy in a "manageable" way). But as the size of the clique you're looking for grows, the problem gets unwieldy in a completely unmanageable way; see the graph shown in the video starting around 4:40.
* As an illustration of this: there's a clique-related problem called Ramsey's problem, which basically boils down to "how big must a graph be such that there is always either a set of n vertices that are completely connected to each other, or a set of n vertices that are completely disconnected from each other?" The mathematician Paul Erdős once said that if an powerful alien force arrived at Earth and said they would destroy us unless we gave them the answer for n = 5, we should marshal all of the Earth's resources, Manhattan-project-style, to find the answer. But if they demanded the answer for n = 6, we should prepare for war.
posted by Johnny Assay at 4:42 AM on April 10, 2023 [20 favorites]
The algorithm you're describing is basically a "brute force algorithm" of the kind described in the caption of the picture at the top of the Wikipedia page, and also mentioned in the subsection "Cliques of fixed size". (And in the video, for that matter — you've just filled in some of the details of the boxes in the flowchart she shows around 4:10.) For a fixed clique size, this algorithm actually does run in polynomial time (i.e., it gets unwieldy in a "manageable" way). But as the size of the clique you're looking for grows, the problem gets unwieldy in a completely unmanageable way; see the graph shown in the video starting around 4:40.
* As an illustration of this: there's a clique-related problem called Ramsey's problem, which basically boils down to "how big must a graph be such that there is always either a set of n vertices that are completely connected to each other, or a set of n vertices that are completely disconnected from each other?" The mathematician Paul Erdős once said that if an powerful alien force arrived at Earth and said they would destroy us unless we gave them the answer for n = 5, we should marshal all of the Earth's resources, Manhattan-project-style, to find the answer. But if they demanded the answer for n = 6, we should prepare for war.
posted by Johnny Assay at 4:42 AM on April 10, 2023 [20 favorites]
Best answer: The main question video asks about the clique problem is "can we find cliques quickly". Your algorithm will find cliques, but it won't do so quickly. As you say, your solution will get unwieldy fast. "Getting unwieldy fast " is a decent informal definition of NP. Meanwhile, problems in P get unwieldy slowly.
Your algo probably grows about as fast as N factorial (7 factorial is 7 x 6 x 5 x 4 x 3 x 2 x 1) which is considered slow, or "NP". An example of a fast algo might grow like N squared does, which is considered fast aka "P".
N squared grows "slowly" : 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169...
N factorial grows "quickly": 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800...
*So far nobody has found a P style solution to the NP problems. However, nobody has been able to prove that no such solutions exist.
posted by mrgoldenbrown at 9:06 AM on April 10, 2023 [2 favorites]
Your algo probably grows about as fast as N factorial (7 factorial is 7 x 6 x 5 x 4 x 3 x 2 x 1) which is considered slow, or "NP". An example of a fast algo might grow like N squared does, which is considered fast aka "P".
N squared grows "slowly" : 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169...
N factorial grows "quickly": 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800...
*So far nobody has found a P style solution to the NP problems. However, nobody has been able to prove that no such solutions exist.
posted by mrgoldenbrown at 9:06 AM on April 10, 2023 [2 favorites]
I think it bears repeating that the interesting thing about P vs. NP is the idea that if there existed a solution that ran in polynomial time for an NP problem, you could reduce all NP-class problems to that and therefore all NP-class problems would become P-class problems. This is what the whole P ?= NP question is about.
Most computer scientists and mathematicians that work in this space tend to think that there is some fundamental difference between P-class and NP-class problems, but as of yet there has been no rigorous way to prove this one way or another, hence why it's one of the more interesting unsolved questions in computer science. If the video was talking about unsolved problems (haven't watched it, sorry), it's most likely that they were referring to P ?= NP, and not any specific NP-class problem (which I believe have to have a solution by definition, it's just that it's going to be an unwieldy one).
posted by Aleyn at 12:38 PM on April 10, 2023 [1 favorite]
Most computer scientists and mathematicians that work in this space tend to think that there is some fundamental difference between P-class and NP-class problems, but as of yet there has been no rigorous way to prove this one way or another, hence why it's one of the more interesting unsolved questions in computer science. If the video was talking about unsolved problems (haven't watched it, sorry), it's most likely that they were referring to P ?= NP, and not any specific NP-class problem (which I believe have to have a solution by definition, it's just that it's going to be an unwieldy one).
posted by Aleyn at 12:38 PM on April 10, 2023 [1 favorite]
"Getting unwieldy fast" is a good defintion for "not P", but it isn't a good definition for NP. NP is about being able to check answers quickly, whereas P is about being able to find answers quickly. Since you can check the answer to any problem in P quickly (by just finding the answer again and seeing if it's the same), every P problem is also an NP problem. There are already algorithms that run in polynomial time for NP problems.
The clique problem is what's called an NP-complete problem, where, if you're given a polynomial-time algorithm, you can use that algorithm to solve *any* problem in NP in polynomial time. It doesn't mean there's no algorithm to solve it -- just that a fast algorithm would also let you solve a lot of other problems quickly.
posted by panic at 3:02 PM on April 10, 2023 [1 favorite]
The clique problem is what's called an NP-complete problem, where, if you're given a polynomial-time algorithm, you can use that algorithm to solve *any* problem in NP in polynomial time. It doesn't mean there's no algorithm to solve it -- just that a fast algorithm would also let you solve a lot of other problems quickly.
posted by panic at 3:02 PM on April 10, 2023 [1 favorite]
Best answer: To put some numbers on this with a back of the envelope calculation:
IIRC, then a 100 group 50-member clique problem gives you 100! / (50! * 50!), or 10^29 possible divisions. (It's 20 for your example problem)
If you can can solve a 6 group 3-member clique problem in 20 nanoseconds, then you are talking roughly 10 trillion years to solve the larger problem.
(There's a high probability I've screwed some detail up above, but the relevant thing is factorial math just explodes with even relatively small increases in input.)
posted by mark k at 3:35 PM on April 10, 2023 [1 favorite]
IIRC, then a 100 group 50-member clique problem gives you 100! / (50! * 50!), or 10^29 possible divisions. (It's 20 for your example problem)
If you can can solve a 6 group 3-member clique problem in 20 nanoseconds, then you are talking roughly 10 trillion years to solve the larger problem.
(There's a high probability I've screwed some detail up above, but the relevant thing is factorial math just explodes with even relatively small increases in input.)
posted by mark k at 3:35 PM on April 10, 2023 [1 favorite]
« Older Looking for an affordable dentist doing partial... | SMS reminder for clients the easy way Newer »
This thread is closed to new comments.
I think iterating over all permutations is generally O(n!), so that would not be a polynomial time solution. (I am not an expert, so someone else may weigh in with a more definitive answer.)
posted by justkevin at 3:23 AM on April 10, 2023 [5 favorites]