Submissions | Add Your Comments | Physics Site Links | Home Page

Email: Radek Hofman

   Radek Hofman

Oct. 26, 2006:
I have read La Theorié de la Complexitié another version of article from Mohamed Mimouni, I have written comments to. This version contain exactly the same errors as previous (refer to my comments below.

Greedy algorithms (hopefully author knows what they are) cannot solve NP-complete problems. There are thousands of counter-examples. Of course they may find correct solution for some particular instances, but so called "proofs" that they are correct ALWAYS are more then unacceptable. Same situwation would be if we generate random solution - it might be correct and optimal... But it is impossible to prove that it always is.

Why then author do not take objections into account, does not answer to them making his text better and continues development of this article?

Sep. 8, 2006:
I have read the paper linked on your site by Mohamed Mimouni Aug. 6, 2006: NP = P La Prouve. The most difficult for me was to read the French text, but fortunately my wife speaks French. This so called “proof” consists of two phases:

1. Walk through graph and prepare n^c Cliques
2. Author realizes that cliques found may be sub-optimal and claims that in the second phase, we need a “different” approach to graph redefining division points to obtain maximum Clique. Well… in graph we have O(2^n) Cliques so proving that this “different” approach to finding a CORRECT solution in POLYNOMIAL time is very difficult, (not to say impossible).

Example:
At first stage, we've got a Clique containing nodes 1,2,3,4,5,6,7,8,9,10 and other Cliques. The maximum Clique in the Graph contains nodes 1,3,5,7,9 – we have to remove nodes from Cliques found in the first phase to be able to add different nodes. It is easy to find examples for every algorithm to lead it into a situation where it will not be able to find a correct solution or the computation time will become exponential.

So until author proves that he knows an algorithm and can PROVE its correctness, please change the title to “prove attempt” or remove it.