You are an expert at summarizing long articles. Proceed to summarize the following text: 
in a novel dynamical approach the @xmath1 vertices of a graph @xmath0 are mapped onto @xmath1 physical points located initially at equal distances from each other forming a symmetric @xmath1 simplex in @xmath2 dimensions . attractive / repulsive forces are introduced between pairs of points corresponding to connected / disconnected vertices in the original graph @xmath0 . we then let the system evolve utilizing first order aristotelian dynamics@xcite . we tune the relative strength of repulsive and attractive forces to be @xmath3 with @xmath4 the average valency i.e. average number of vertices connected to a given vertex so as to have no net average repulsion / attractions . we found , that as the system evolves various physical clusters of points tend to form . these physical clusterings reveal clusters ( or imperfect cliques ) in the graph - namely groups of vertices with a larger than average mutual connectivity . also the matrix of distances @xmath5 between the various points @xmath6 and @xmath7 is characteristic of the graph topology : points corresponding to vertices which are `` close in the graph '' namely have ( relatively ) many , short , paths connecting them will move closer together and conversely , points which are `` far in the graph '' tend to move apart . the distance matrix and clusters are important graph diagnostics . in particular the first allows us to solve easily the graph equivalence problem namely to decide if two connectivity matrices @xmath8 and @xmath9 correspond to the same topological graph and if they do to find the relabelling of vertices which makes @xmath10 and @xmath11 identical .    these results are of considerable practical importance . still neither of the above problems belongs in the special class `` np complete '' problems . the latter consists of problems such as the travelling salesmen problem and the satisfiability problem for which a putative solution can be readily checked in polynomial time yet no polynomial solution method is presently known@xcite . many of these problems can be phrased in terms of graphs as the task of finding some specific graph @xmath12 inside bigger graph @xmath0 . further , all these problems which superficially seem very different are at a basic level , equally difficult : if a method of solution in polynomial time is found for one such problem then all the problems should be solvable in such time by essentially the same method . conversely if we can prove that just one npc problem necessarily require , non - polynomial time for its solution , the same holds for all of them . two of us have recently conjectured@xcite that a new variant of our approach namely of dynamically docking rigid simplexes @xmath13 and @xmath14 representing @xmath12 and @xmath0 can solve the `` g inside g '' problems . here we wish to present the first concrete application of the original , point translation or single simplex distortion algorithm ( sda ) , to an npc problems namely that of finding the largest perfect clique in @xmath0 . to most clearly illustrate the essence of the problem we consider the `` students in dorm '' example used in the general description of the clay institute prize offered for resolving @xmath15 problem@xcite . we have @xmath16 students out of which we need to select @xmath17 which can live together in a dorm , subject to a very long list of mutual exclusions . this list states that student # 1 can not be together with any one student from a specific set of say 200 other students , student student # 2 can not be together with any one from another partially overlapping set with a comparable number of students etc . how can we pick up a set of 100 students such that any one is completely compatible with the other 99 , and what is this set ? clearly this is a particular example of the general satisfiability problem where the conditions imposed are just `` two body '' exclusions . it is also a particular case of looking for a graph @xmath12 inside @xmath0 where @xmath12 is a perfect clique of vertices each of which is connected to all other members in the clique . we encode into @xmath0 with @xmath16 vertices the various mutual exclusion constraints by not connecting with edges vertices @xmath18 and @xmath19 if student # i and student # j are not compatible , and connecting by edges compatible pairs . clearly if we find within @xmath0 a clique with @xmath1 vertices it means , by our very construction , that the students to which these vertices correspond are indeed all mutually compatible . we could construct in judicious manner various smaller consistent subsets , and try piece them together . often , however a new inconsistency is revealed and we need to pursue other alternatives . while we certainly can do this in far less steps than @xmath20 the difficulty of the problem seems to grow at least exponentially with @xmath1 .    in desperation we might decide to resort to the following primitive alternative and simply let the 400 students `` fight it out '' . in this all out war each student will try to push away members which are inconsistent with him and pull in those which are . this collective natural selection of the `` compatible '' - which may well be a prerelevant social phenomena - would hopefully leave us with the desired large group of mutually consistent individuals . unfortunately the outcome of such a 400 way `` somo '' fight of staying in the ring is strongly biased by the initial arbitrary placement of students in the two dimensional arena@xcite . thus we could envision a situation where an ideal group of completely compatible dorm candidates is placed in the center of a group of highly unpopular ones and is `` ejected '' together with them . in order to generate the correct large clique we need to completely unbias the starting position and avoid the severe constraints due to our existence in a physical world with limited number of dimensions . this can be done only if we go to @xmath21 dimensions and place the `` students '' which , in the inverse problem that we are really after , are metaphors for the physical points representing the @xmath22 vertices of the graph , at the vertices of a symmetric @xmath22 simplex . our search for perfect cliques uses the same physically motivated dynamical algorithm previously developed to identify via the physically bunched points clusters or `` imperfect cliques '' in a graph@xcite . we found that to adapt this algorithm for the present purpose we need only to enhance the ratio of the repulsive and attractive interactions . originally it was chosen to be : @xmath23 which could be relatively small . thus for an average valency of @xmath24 in a graph with @xmath25 vertices it is only @xmath26 . however , in order to meet the criteria of _ perfect _ cliques we clearly have to significantly enhance the strength of the repulsive interactions so as to avoid points which are connected to a fairly large number of the points in the clique but not to all of them from joining in . thus in the first round of applications we used @xmath27 we first considered a small clique of @xmath28 in a graph with @xmath29 vertices with the connectivity matrix of fig.([fig : clq - c ] ) . in addition to the clique this matrix consists of six clusters with randomly created internal connections with average valency @xmath31 . these clusters , in turn , have been randomly interconnected with a large valency @xmath32 . to simulate a real - life situation of networks with unknown structure ( topology ) we randomly permute the rows and columns of the matrix @xmath10 obtaining the reshuffled matrix @xmath33 shown in the fig.([fig : clq - b ] ) .      next we apply our algorithm for clusters reconstruction using equal attractive and repulsive constant forces in @xmath34 dimensional space . the vertices of the 100-simplex were allowed to move under the influence of the forces on the 98-dimensional hyper - sphere in 99-dimensions . after a number of steps we analyzed the mutual distances between the vertices of the simplex and group neighbors which are close to each other into cliques . the new cluster - connectivity matrix is shown in fig.([fig : clq ] ) .        to see how the algorithm works for the case of overlapping cliques we considered two examples . the first example includes two cliques @xmath30 and @xmath35 with a @xmath36 overlap on a `` background '' of a @xmath37 matrix with the same average @xmath32 connectivity as above . the corresponding connectivity matrixes before reshuffling is shown in fig.([fig : clq2-c ] ) . the second example involves two of cliques @xmath24 with a large overlap of @xmath39 in fig.([fig : clq3-c ] ) . our reconstruction yields one clique of @xmath24 and one of @xmath39 fig.([fig : clq3-cl ] ) . as expected we fully reconstruct the largest cliques . this is done at the expense of correspondingly reducing the size of the reconstructed part of the overlapping smaller or equal size cliques . other examples involve a @xmath17 clique in a @xmath16 graph corresponding to the `` students in dorm '' question . in addition we had an imperfect clique or cluster of @xmath41 with average valency of @xmath31 on a background of @xmath32 ( fig.([fig : clqnp - c ] ) ) . the successfully reconstructed @xmath25 clique after reshuffling is shown in fig.([fig : clqnp - cl ] ) . fig.([fig : clqnp3-cl ] ) shows the reconstructed results after reshuffling . the clique is imperfectly reconstructed . however , increasing @xmath45 from one to two improves the reconstruction as shown in fig.([fig : clqnp3-cl2 ] ) . the above results are to our mind fairly impressive . these results show that by mild tuning our original code solves in very short time and for many cases the npc problem of the largest clique . it may still fall short of solving it in all cases . as a worst case scenario we could envision a vertex ( or several such vertices ) which are connected to all the vertices in the clique save one . to avoid these vertices from joining the clique even in this case , rendering it imperfect , we need that the single repulsion due to the missing edge , overcome all the @xmath2 attractions to the rest of the points in the clique . thus the strict perfect clique worst case scenario demands @xmath46 this wildly differs from the above eq.(refx ) : for a graph @xmath0 with @xmath25 vertices @xmath47 and a clique of size @xmath48 we need a factor hundred enhancement of the ratio @xmath45 from @xmath26 to @xmath24 ! our @xmath49 based intuition would strongly suggest that this stops formation of all cliques , perfect or not , since as any given point tries move towards its `` designated '' clique it may be `` overwhelmed '' by the many repulsive forces which will prevent it from joining the clique . the configuration with the perfect clique ( and the largest perfect clique in particular ) fully formed i.e having all its vertices collapse at a point is indeed the desired final lower energy state . however there may be false local minima which trap our system just like in spin glass@xcite and protein folding problem@xcite . this is indeed most certainly the case for `` low '' dimensionalities . however with @xmath50 , as is the case here , the above intuition fails . specifically any one given `` test point '' feels just as many different forces in the directions of the other particles namely @xmath51 as there are independent directions @xmath21 to move in . ideally therefore the test particle should be able to simultaneously respond to all different @xmath51 forces , move in the direction of all the attractors and away from all the repellers and in the process further lower the energy of the system . we can adopt a local , non - orthogonal , system of coordinates where the @xmath51 axes are aligned along the unit vectors pointing from @xmath52 - the chosen point , to @xmath53 the other @xmath51 points . using our choice of constant forces@xcite we have then a net force @xmath54 which is the sum of the unit vectors along these axes with + and - signs . since these are @xmath51 linearly independent vectors the sum never vanishes @xmath55 always and no local minimum arises . there is one `` small '' correction however to the above argument . it is due to the fact that in our original algorithm we have introduced one further constraint on the motion of the points , namely that at all times on the unit circle @xmath56 . it seemed necessary in order to avoid running away to infinity of repelling vertices or collapse to the origin of attracting ones . this does however introduce an extra normal reaction force that could in fact cancel the above sum in eq.([z ] ) , and thus yields local minima . hence in the final runs we did not impose this constraint . instead we modified our code to facilitate handling the increasing distances between points at later stages of the evolution . we found that our program fully reconstructed the maximal clique@xcite . this happens regardless of the degree of the connectivity of the random background and also of the existence of large and partially overlapping slightly smaller cliques . thus for the n=100 maximal clique in an n=400 vertex graph ( i.e the students choice for dorm problem ) we added two 80x80 cliques which overlapped our 100x100 clique in two 60x60 patches which , in turn , had a 20x20 overlap and used a background with 70% connectivity fig.([fig : c3in400 ] ) . even under such seemingly unfavorable conditions we reconstructed our clique fig.([fig : cl3in400 ] ) . v. gudkov , j.e . johnson and s. nussinov , arxiv : cond - mat/0209111 ( 2002 ) . v. gudkov and s. nussinov , arxiv : cond - mat/0209112 ( 2002 ) . s. nussinov and z. nussinov , arxiv : cond - mat/0209155 ( 2002 ) . t. sudkamp , `` languages and machines : an introduction to the theory of computer science '' , addison - wesley , 1997 . clay institute , http://www.claymath.org/prizeproblems/pvsnp.htm . social pressures / encouragement via nasty / favoureble communications are not limited by dimensionality - explaining its vast power and magically efficiency . m. mezard , g. parisi and m.a . virasoro , `` spin glass theory and beyond '' , world scientific , singapore , 1987 . bryngelson and p.g . wolynes , j. phys . chem . * 93 * , p. 6902 this choice common to the present and earlier works , was originally made for simplicity . in retrospect it turns to be optimal . indeed if the forces - or potentials become too strong at short distances , then two points which attract each other , may prematurely `` seize '' and become inseparable - a phenomenon which is a source of the deleterious multiple local minima . the general convexity condition for the potentials @xmath57 which avoids this difficulty -and which our linear potential trivially satisfies- has been pointed to us by vassilios s. vassiliadis ( private communication ) . once we find a substantial portion @xmath58 of the vertices belonging in the perfect clique the construction of the rest of the clique can be easily completed as follows : we omit from our graph g all those vertices which do not connect to all the vertices in the clique . this will drastically reduce the number of vertices in the remaining relevant part of g and vastly accelerate the remaining calculations .
a novel approach to complex problems has been previously applied to graph classification and the graph equivalence problem . here 
 we apply it to the np complete problem of finding the largest perfect clique within a graph @xmath0 .