![]() |
Michael LaPlante's paper on NP=P
I read the paper of "Michael LaPlante" entitle "A polynomial time algorithm for solving clique problems" and here is my commecnt on the paper: Author claim that have a polynomial algorithm for Maximum Clique and K-Clique problems. The algorithm first finds the 3-Cliques, obviously this process is polynomial because only n*(n-1)*(n-2) ternary relation exists. And we can easily find whole of them in a n^3 process. But then author wish to assemble them to produce cliques of bigger sizes. As I see in figure 3F , 3H, 4F, 4I I think author only consider the case when algorithm begins to merging, it only merges the cliques they are maximum where when you have a graph of 100 or 1000 nodes you may begin to mergeing but the nodes that you merged be wrong having a bigger clique using defferent merging process. In fact the problem is that when you want to merge them, there are many decision points and milions number of different merging process. Yes it is complexity of NP-Completes! let me know if I'm wrong. Thus the algorithm is only a greedy algorithm that finds some cliques but dont garantee they be maximum clique or bigger than a special number K. In fact the algorithm is correct if you add try and error to it but is not polynomial. Best wishes, Kavosh Havaledarnejad Icarus.2012@yahoo.com |
زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۹:۵۱ قبل از ظهر ميباشد. |
Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.