A good introduction to the mistery of the P vs. NP problem is to examine polynomial-time algorithms which ‘almost’ solve an NP-complete problem. Usually such algorithms solve the problem for most inputs, and ‘only’ fail at some quite rare ‘evil’ special inputs. Here I present such an algorithm of mine. I don’t even know for which kind of evil inputs it fails. (It probably fails for some inputs of course, it is just harder to provide counterexamples than to come up with the algorithm itself.) The reason that I present this algorithm is that I want to demonstrate a rarely considered possibility: Maybe P equals NP, maybe we will even find the algorithm which is not that incredibly complicated, we will use the algorithm in practice, but it will be crazily hard to prove that the algorithm is correct because the algorithm is based on pseudorandom behaviour (a.k.a Monte Carlo method) and some kind of ’emergent’ behaviour instead of a simple direct, easily analyzible behaviour.
So here is an algorithm which tries to find an N/2 clique in a graph. (A clique with half of the vertices.)
Please note that it is enough to find one vertex which is surely not in the clique. Then we can recursively use the algorithm for the remaining vertices, and it is easy to see that we will still be in polynomial time.
At the beginning let’s erase those vertices which has less then N/2-1 neighbours.
Let’s call the vertices ‘guys’. The ones in the N/2 sized clique are the good guys, the other N/2 guys are the bad guys. The good guys form a clique. The bad guys decide how they connect with the good guys and with each-other. They intentionally try to ‘game’ the system, they intentionally connect in tricky ways to make our algorithm fail.
Now we randomly distribute the vertices into two N/2 sized distinct sets:
– The good set.
– The bad set.
We repeat the following for a reasonable time: (let’s say N^5 times)
We randomly select two guys in the good set which are not connected. We replace them with two randomly selected guys from the bad set.
Please note that when we do such a replacement, then we do one of the following 2 things (without knowing which case we are dealing with):
– We throw out two bad guys from the good set.
– We throw out one bad guy and one good guy from the good set.
So we never throw out two good guys!
During this N^5 steps, we note for each vertex for how many time it stayed in the good set. Let’s call it T(n). It is easy to see from the above that the good guys together have a better summa T(n) than the bad guys.
But of course the bad guys can do evil trics. They can create some ‘bad superstars’. These are connected with almost every good guys and almost every bad guys. These can have very good T(n). This does not hurt us though, because we are only interested in the ‘worst’ guy. But they can do even more evil tricks. They can chose two good guys which they don’t connect with. And they connect with good guys and each other very much, on the borderline of creating another N/2 clique (but not creating, because they are not allowed to.) These bad guys, when get into the good set, they throw out these two good guys (while throwing themselves out, but they are in superior numbers.) The two poor good guys can end up having the worst T(n)-s.
But we don’t give up. The T(n)-s represent something about ‘goodness’. We just have to extract some minimal tiny bit of information from this.
We order all the guys according to their T(n)-s.
We mark the best N/2 the ‘goods’, the others the ‘bads’.
Now we give ‘points’ to vertices according to how many good neighbours they have. (Maybe we should somehow penalize bad neighbours, but I am not sure, because this way bad guys could just make harm to good guys by connecting to them.)
Now we order the guys according to points, we call the best N/2 the goods, the other N/2 the bads…
We repeat this let’s say N^5 times. The idea is that good guys are that guys who know very much good guys. Those two poor good guys in the previous example are coming up…
We assume, that the guy with the least points in the end is a bad guy.
This algorithm probably fails for some inputs. (I don’t know for what kind of inputs yet.) The real question is that: can it be fixed? Is this really fundamentally impossible, or just a bit more tricky than we first thought?