Re: SAT is in P, CLIQUE is in P
- From: "Matt Zellman" <matt.zellman@xxxxxxxxx>
- Date: 4 Sep 2006 17:07:39 -0700
mimouni wrote:
mimouni a écrit :
Proginoskes a écrit :In the case of a graph not to modify, one changes the order of the
Eric Schmidt wrote:I gave the example, only to render comprehensible, the mechanism. The
mimouni wrote:
Proginoskes a écrit :
Proginoskes wrote:
mimouni wrote:
A deterministic polynomial algorithm for clique has been just found. If
you know French you can have it on:
http://www.wbabin.net/science/mimouni.pdf
What proves that NP=P.
A 2-page paper? I don't think so.
(I'll put it through Babelfish anyway, so that I can read it.)
Thanks to Berge's index of definitions (from _Graphs and Hypergraphs_,
1973), I was able to extract the graph-theory terms. (The list of
definitions also gives translations into French and German. This is
very useful, because when I took German a long time ago, I never
learned any Graph Theory terms. 8-) )(There's also a typo in the paper.
"Moine" should be "moins".)
But the algorithm doesn't work. Let G be the graph with vertices
{1,2,3,4}, where 1 is adjacent to 2, 3, and 4, and 3 and 4 are
adjacent. Then if you go through the procedure, where the vertices
1,2,3,4 are taken in that order, Clique 1 ends up being {1,2}, and
Clique 2 is {3,4}, neither of which is maximum (as {1,3,4} is a clique
of size 3).
Mimouni might also be confusing "maximal" and "maximum" here. A clique
C is maximal if for each vertex v not in C, v is not adjacent to some
vertex in C. A clique is maximum if it has at least as many vertices as
any other clique.
A maximum clique is maximal, but not the other way around. (See the
example I gave above.)
--- Christopher Heckman
P.S. A rough translation:
NP=P
Author: Mohamed MIMOUNI.
Email1: mimouni.mohamed@xxxxxxxxx
Comments: 2 pages.
Subj - Class: The theory of complexity.
Abstract: I give the polynomial algorithm to solve CLIQUES. This
algorithm makes it possible to find maximum cliques in a simple
undirected graph, which implies that NP=P.
The key is the following: Let G be a simple undirected graph, S a given
vertex and C a clique of G.
Then can S be added to C? This problem is a deterministic polynomial
problem, because the answer is "yes" if all the vertices of C are
adjacent to S, which can be checked in polynomial time, whereas the
answer is "no" if there is at least one vertex of C which is not to
adjacent to S.
The Algorithm
Let G be a simple undirected graph with n vertices.
Each vertex could be in at least one clique. We will denote each clique
by successive numbers. Then here are the stages:
1. The first vertex S1 will be in Clique 1.
2. Choose a second vertex S2; if it is adjacent to S1, then it will be
put in Clique 1; if not, it will be put in Clique 2.
3. Choose a third vertex S3; if it is adjacent to all the vertices in
Clique i (i = 1 or 2), it will be added to Clique i; otherwise, it will
be put in Clique 3.
4. This procedure will be continued for all vertices. This part can be
done in polynomial time.
5. After this procedure, a second "pass" will be made, where one
notes all cliques that each vertex is in.
6. The clique that contains the largest number of vertices will be a
maximum clique.
The problem INDEPENDENT SET will be solved by choosing only one vertex
in each of the cliques which are obtained, provided that it is not in
another clique. This works since two different cliques each have a
vertex, which are not adjacent to each other.
Thank you Proginoskes, for your interest. Can be that I do not have
to render comprehensible the algorithm well. For your counterexample,
the top 1 is at the same time in clicks 1 and clicks 2, which leads to
one clicks maximum {1, 2,4}, because the procedure will be in this
manner:
1. Vertex1 in clique1.
2. Vertex2 in clique1, because vertex2 is to connect to vertex1.
3. Vertex3 is not connected to the vertex2, therefore it is in clique2.
4. Vertex4 will be in clique2 only, because in clique1 the vertex2 is
not connected to the vertex4.
As you had written one obtains two clicks: clique1 with two tops, and
clique2 with two tops. However note 5 of this algorithm announces that
a second turn should be made what will put vertex1 in clique2,
therefore the clique2 contains three tops and not two.
If I'm understanding you correctly, in step 5, the algorithm loops over
all vertices and cliques,
No algorithm that considers all cliques (even if it only considers all
maximal cliques) can run in polynomial time; the m-partite graph K_{2,
2, ..., 2} has 2^m maximal cliques, which is
2^(n/2) = (sqrt(2))^n, and that's exponential in the number of
vertices.
adding a vertex to a clique whenever it is
adjacent to each vertex already in the clique.
You neglected to prove that your algorithm works as claimed.
Mimouni has yet to include _any_ kind of proof; it will be very hard to
publish a paper without proofs in it. (Ask James Harris; he's had some
experience with this.)
Anyway, even with the "second pass", it doesn't work:
Suppose there are 6 vertices in the graph. Vertices 2, 4, and 6 form a
clique of size 3. Additionally, there are edges between vertices 1 and
2, between vertices 3 and 4, and between vertices 5 and 6.
Processing the vertices in order from 1 to 6, after step 4 we have {1,
2}, {3, 4}, and {5, 6} as our cliques. However, none of these is a
subset of the unique maximum clique {2, 4, 6}, so there is no way the
second pass could find it. Indeed, in this case it simply leaves the
cliques unchanged.
Richard K. Guy discovered a principle called The Strong Law Of Small
Numbers, which basically say that small numbers are not good numbers to
look at as possible counterexamples; "typical" numbers are "big". The
same seems to apply to graphs. Mimouni might be able to prove his
algorithm works for the small graphs he chooses.
A good test of a clique-finding algorithm is to take a random graph
G(n,p) and add a clique of size k to it (where the vertices are chosen
at random, of course), and then looking to see whether the
clique-finding algorithm can find it. Mimouni might want to try this
with n=100. (A random graph with
p = 1 / C(n,k)^C(k,2)
is expected to have one clique of size k; so he might want to let p be
a constant fraction of this expression. "Random graph" means to include
an edge between u and v with probability p, choosing a different random
number each time.)
--- Christopher Heckman
partie1 is it deterministic, or not deterministic?
For can the random graph, you give me a program which to generate this
type of the graphs?
For the partie2, the critical case is when one cannot modify the graph,
for that there are three methods, and I test to find most adequate.
That will take time.
vertexes, if (a, b) is edge which is not in none clique to find in
partie1, takes (A) then (b) of them.
Once you have to reassign the order of the vertices, it ceases to be a
polynomial time algorithm, because it cannot be guaranteed that the new
order will be any more successful than the initial order.
.
- References:
- Re: SAT is in P, CLIQUE is in P
- From: mimouni
- Re: SAT is in P, CLIQUE is in P
- Prev by Date: Re: An uncountable countable set
- Next by Date: Re: Powers of 5
- Previous by thread: Re: SAT is in P, CLIQUE is in P
- Next by thread: Re: SAT is in P, CLIQUE is in P
- Index(es):
Relevant Pages
|
