SAT is in P, CLIQUE is in P
mimouni
you know French you can have it on:
http://www.wbabin.net/science/mimouni.pdf
What proves that NP=P.
Proginoskes
A 2-page paper? I don't think so.
(I'll put it through Babelfish anyway, so that I can read it.)
--- Christopher Heckman
Proginoskes
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...@gmail.com
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.
mimouni
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.
Proginoskes
The term for "summet" in English, in Graph Theory, is "vertex" (or
"point"). And the spelling is "cliques" (or "complete graphs"), not
"clicks".
> 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.
Okay; this was the step that I was wondering about, because the
translation wasn't clear. I'll have to think about it, but I don't
think this clarification will work, either.
(For one thing, a graph on n vertices might possibly have a^n maximal
cliques, where a is a real number greater than 1, and since you're only
examining a polynomial number of maximal cliques (in fact, you only
consider n cliques, at that), you might easily miss the maximum
clique.)
((LATER:)) Actually, this corrected algorithm won't work, either. Let G
be the graph with vertices 1,2,3,4,5,6 and the edges 13, 15, 35, 12,
34, 56. Then Clique 1 ends up being {1,2}, Clique 2 ends up as {3,4},
and Clique 3 ends up as {5,6}. {1,3,5} is the maximum clique in G.
--- Christopher Heckman
Eric Schmidt
If I'm understanding you correctly, in step 5, the algorithm loops over
all vertices and cliques, 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. 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.
--
Eric Schmidt
--
Posted via a free Usenet account from http://www.teranews.com
Proginoskes
That was how I interpretted it, and I posted this same counterexample
about an hour ago. But yes, the paper doesn't include a proof of
correctness. (Clearly it's polynomial ...)
--- Christopher Heckman
Proginoskes
In fact the statement in parentheses is true. As David G Radcliffe
pointed out in 1999 (in a sci.math post in: Re: A hard question, need
your help), the graph complete tripartite graph K_{m,m,m} has 3^m =
(3^(1/3))^(# vertices) maximal cliques in it. (The clique number of
K_{m,m,m} is 3.) So no modification of Mimouni's algorithm will work.
Proof: Choose an m, and run Mimouni's algorithm on G = K_{m,m,m} on it,
where V(G) = {1,2,...,3m}. Let C(1), C(2), ..., C(b) be the cliques
that G finds. If m is large enough, these will not be all of them, so
suppose {u,v,w} is such a clique, where we can also assume min(u,v,w)
is greater than 1. Now let H be the graph G with a new vertex x,
adjacent to u, v, w. Then H has a clique of size 4, but when the
algorithm is run on H, the first b cliques will be the same as for G,
and the (b+1)st will include {1,x} but not u. Hence the clique of size
4 is missed by the algorithm, showing that it does not work.
--- Christopher Heckman
Proginoskes
A couple things need to be fixed: The new vertex should be the number
(3m+1), and it should also be adjacent to 1.
> Then H has a clique of size 4, but when the
> algorithm is run on H, the first b cliques will be the same as for G,
> and the (b+1)st will include {1,x} but not u. Hence the clique of size
> 4 is missed by the algorithm, showing that it does not work.
This will show that you cannot focus on a polynomial number of cliques,
while using the vertices in the same order. Of course, there _is_ an
ordering of the vertices where Mimouni's algorithm will work, namely:
list all the vertices in the maximum clique, then the rest. But you
need to know the clique is there first.
mimouni
Proginoskes a écrit :
Hello, Proginoskes, thank you very much for your assistance, but NP=P;
it is necessary to add a new procedure and here the correction:
1st part :
1. The first S1 sommet will be in the clique1.
2. One takes second S2, if it is connected to S1 it is in clique1, so
not it will be In clique2.
3. One takes third S3, if it is to connect has all the Vertex of
clique1 it will be In clique1, if it is to connect has all the Vertex
of clique2 it is in clique2, So not it will be in clique3.
4. One makes procedure for all the Vertex: if a sommet is to connect
with all The Vertex of same cliques it will be to add to this cliques,
so not it will not be To add (it is in polynomial time).
5. After treathaving treated all the Vertex, one will have obtained
several cliques. But not All cliques them of G.
2nd part :
The first part, distributes the Vertex of a graph, in cliques to
separate the one with Others. From finish this note, one obtains
several cliques, but the first part Do not detect all cliques them,
then a second procedure must be made. This time One seeks under graph
of G, which contains the Vertex which are not in Cliques found in the
first part. With this remark, one makes the algorithm (1st part),
another time for the new one Graph obtained. And one Vertex when one
does not find any more of the Vertex which do not have was placed In
one cliques. Cliques which contains more numbers of the Vertex, will
be thus, one cliques maximum.
i m sorry but t not speak englisch.
Mariano Suárez-Alvarez
> i m sorry but t not speak englisch.
Oh well. Then write up your paper (that pdf file you
posted needs lots of work, apart from the math:
get it proofread by someone who knows a bit of
French spelling) and send it to any journal
dealing with combinatorial optimization, complexity
theory or something releated. It'll get refereed, and,
if it is accepted, published. Write it in French if you
prefer French: I am quite sure no journal editor in
his right mind would reject a correct proof that
P=NP because the language of the paper is French.
But you need to write up the details: you cannot
keep introducing modifications and corrections.
I am far from convinced that you even have a working
algorithm. That should not be a problem, as
I with probability one will not be your referee!
-- m
mimouni
Mariano Suárez-Alvarez a écrit :
ok, gives me a graph, with 300 vertices and 22425 edges. if you cannot
me a graph gives gives the density is close to 0.5, and I give you
clicks it maximum in less than 16 heures.
Proginoskes
I think I got what you were trying to say.
If you're trying to find all the cliques of G, you may have to use
exponential time.
I gave a family of graphs earlier which is still applicable. If G is
K_{3,3,3,...,3}, where there are m 3's, then G has 3^m maximum cliques,
which is exponential in the number of vertices of G (which is 3m). I
showed how to add a new vertex (and new edges) to G to get a graph
where your old algorithm failed. I think the same idea shows that your
new algorithm doesn't work, either.
--- Christopher Heckman
mimouni
Proginoskes a écrit :
The objective is to prove that NP=P, if you can gives me graphs
difficult to find cliques it maximum, or a 3-SAT which is well on
satisfiable. If I give the answer, the algorithm deserves a particular
intention.
Mariano Suárez-Alvarez
No, it does not work like that. The algorithm deserves
attention only if it is correct. You may have an heuristic, which
---if it indeed tends to work---would be interesting (I guess)
but would most certainly not prove that P=NP.
In any case, even if you were able to solve "challenge"
instances, that would not prove anything, as an
algorithm may well be, say, O(e^n) but with the
constant implied by the O extremely small so as
to make small instances (where by small I mean not
arbitrarily large) approachable.
-- m
Proginoskes
Any paper that claims to have a clique algorithm must have a proof that
it is correct. Even if the object is to show that the algorithm works
for graphs which arise from 3-SAT graphs, a proof needs to be supplied,
and Mimouni has not produced anything even remotely resembling a proof.
(I'm not singling out Mimouni here, of course; I don't believe that
Ibrahim Cahit's "Spiral Colorings" can be proven to work, even though
it appears to be a useful heuristic which works in many contexts.)
However, if it can be shown that there is a poly-time algorithm (A) for
finding the maximum clique in a "3-SAT graph" (a graph which arises
from the CLIQUE/3-SAT reduction), then there is a poly-time algorithm
for finding the maximum clique in any graph. This is true because of
the fact that if it can be shown that any NP-complete problem is in P,
then P=NP immediately follows:
There is a poly-time reduction for the CLIQUES problem to 3-SAT, for an
arbitrary graph G; the question about whether there is a clique of size
k in a graph G can be converted into a 3-SAT formula F which is
satisfiable iff G has a clique of size k. (This is because CLIQUES is
in NP.) This 3-SAT formula F can be converted into a graph H (which is
actually a 3-SAT graph)(since CLIQUES has been proven to be
NP-complete), and then Algorithm A will supply values of the Boolean
variables satisfying F (if some set of values exists), and this set of
values will determine whether there is a clique of size k in G.
(Once you have a poly-time algorithm for the decision problem as to
whether there is a clique of size k in G, it can be extended to a
poly-time algorithm to find the size of the largest clique in G, simply
by letting k = 1, 2, 3, ..., |V(G)| and seeing how large k can be
before you get a NO answer.)
--- Christopher Heckman
mimouni
phase?
For the first version of this algorithm, had given you against example,
and i made a second version. Maintaining the algorithm by two part is
devised, in the first each time one at a vertex and a finished number
of clique and one please know if one can add the vertex in this clique
or not (it is polynomial). And if the vertex can be in none of these
clique, it (the vertex) will be in new cliques. When one finished one
will find a number finished of clique, but not all clique them, then
one passes to the second part, here one removes each edges which is in
one cliques to find in the first part, therefore one obtains a new
graph of small size. And one repeats the algorithm for this new graph,
to find the others cliques.
Proginoskes
> phase?
I don't know what this question is supposed to ask. For instance, "NP"
does not mean "non-polynomial"; it means "non-deterministic
polynomial".
> For the first version of this algorithm, had given you against example,
> and i made a second version. Maintaining the algorithm by two part is
> devised, in the first each time one at a vertex and a finished number
> of clique and one please know if one can add the vertex in this clique
> or not (it is polynomial). And if the vertex can be in none of these
> clique, it (the vertex) will be in new cliques.
Okay; this is phase 1.
> When one finished one
> will find a number finished of clique, but not all clique them, then
> one passes to the second part, here one removes each edges which is in
> one cliques to find in the first part, therefore one obtains a new
> graph of small size. And one repeats the algorithm for this new graph,
> to find the others cliques.
But how do you know that if you remove an edge from a maximal clique of
G, that any maximum clique will still remain? In other words, an edge
might be in two maximal cliques. If you start with the "diamond graph"
D, which is K_4 with an edge removed, and delete the edge whose ends
are the vertices of degree 3 (to get a 4-cycle), you've wiped out both
maximum cliques of D.
In any case, an earlier criticism applies: How do you know that you end
up with a maximum clique?
--- Christopher Heckman
mimouni
1 {2; 9} wants to say that 1 is adjacent with 2 and with 9.
1 {2; 9} |2 {3} |3 {4} |4 {5; 7; 8} |5 {6} |7 {8; 9} |8 {9}
After the parte1: clq1: {1; 2} |clq2: {3; 4} |clq3: {5; 6} |clq4: {4;
7; 8; 9}
After the parte2, the new graph is (2; 3; 4; 5; 9):
clq5: {2; 3} |clq6: {4; 5} |clq7: {1; 9}
clq4 is clique maximum.
I gave this example so that the mechanism of the algorithm is clear.
after the parte1, the edegs like (1; 2) (2; 3) (4; 5) and (1; 9) are
not in cliques 1,2,3 and 4.
that gives like new graph: (2; 3; 4; 5; 9)
matt.z...@gmail.com
Graphs of the following family are all counterexamples to your
algorithm. I can't immediately see a good fix for the problem.
on 8 vertices:
12, 13, 14, 18, 25, 27, 28, 34, 35, 37, 46, 57, 67, 68, 78
(a 4-clique surrounded by 8 triangles, with the vertices in the outer
ring numbered 1468 and the vertices in the inner ring--the maximum
clique--numbered 2357)
on 10 vertices:
12, 13, 19, 1A, 23, 24, 25, 35, 36, 38, 3A, 45, 46, 47, 56, 58, 5A, 68,
6A, 78, 79, 89, 8A, 9A
(a 5-clique surrounded by 10 triangles, with the vertices in the outer
ring numbered 12479 and the vertices in the inner ring--the maximum
clique--numbered 3568A)
and on 12 vertices:
12, 13, 1B, 1C, 23, 24, 26, 28, 2A, 2C, 34, 35, 45, 46, 48, 4A, 4C, 56,
57, 67, 68, 6A, 6C, 78, 79, 89, 8A, 8C, 9A, 9B, AB, AC, BC
(a 6-clique surrounded by 12 triangles, with the vertices in the outer
ring numbered 13579B and the vertices in the inner ring--the maximum
clique--numbered 2468AC)
I think you get the idea...
Whenever the first vertex counted is on the outer ring and no three
consecutively numbered vertices are on the inner ring, the algorithm
will return a maximum clique of size 3.
Proginoskes
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
mimouni
Proginoskes a écrit :
I gave the example, only to render comprehensible, the mechanism. The
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.
mimouni
mimouni a écrit :
In the case of a graph not to modify, one changes the order of the
vertexes, if (a, b) is edge which is not in none clique to find in
partie1, takes (A) then (b) of them.
Matt Zellman
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.
mimouni
all the possible orders are made it will be an exponential time.
However, it is not the case. In the first part the algorithm find
clique, but not all clique them, to find the others it is necessary to
find the edges which are not in none clique to find, after the order is
done according to the this edges. That gives the new one clique, for
example if the edges (a, b) is not in none clique, if I start with the
vertex (A) then (b), I would be assured that I find at least new
cliques.
G.E. Ivey
Proginoskes
Then it is worth repeating: Some graphs have exponentially
(non-polynomial number) many maximal cliques. If you want to consider
them all, you will end up with an algorithm which is not
polynomial-time.
--- Christopher Heckman