Computation of Ramsey Numbers by P Systems with Active Membranes

January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 COMPUTATION OF RAMSEY NUMBERS BY P SYSTEMS WITH ACTIVE MEMBRANES LINQIANG PAN Image Processing and Intelligent Control Key Laboratory of Education Ministry Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, Hubei, China [email protected] DANIEL D´IAZ-PERNIL and MARIO J. P´EREZ-JIM´ENEZ Department of Computer Science and Artificial Intelligence, University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] [email protected] Ramsey numbers deal with conditions when a combinatorial object necessarily contains some smaller given objects. It is well known that it is very difficult to obtain the values of Ramsey numbers. In this work, a theoretical chemical/biological solution is presented in terms of membrane computing for the decision version of Ramsey number problem, that is, to decide whether an integer n is the value of Ramsey number R(k, l), where k and l are integers. Keywords: Membrane computing; P system; Ramsey number. 1. Introduction In 1930 the British mathematician Frank P. Ramsey published a paper that has led to a research area called Ramsey Theory [8]. Ramsey-type theorems have roots in different branches of mathematics and the theory developed from them influenced such diverse areas as number theory, set theory, geometry, ergodic theory and theoretical computer science [9]. Ramsey-type theorems are showing that a total disorder is impossible. Specifically, Ramsey theory studies conditions when a combinatorial object necessarily contains some smaller given objects. The role of Ramsey numbers is to quantify some of the general existential theorems in Ramsey theory. For integers k, l ≥ 2, the classical 2-color Ramsey number R(k, l) is defined as the least number n = n(k, l) such that for every 2-coloring (say red and green) of the edges of the complete graph Kn on n vertices, Kn contains either a clique of January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 order k with red edges or a clique of order l with green edges. It is well known that the clique problem is an NP-complete problem [2]. Furthermore, computing a lower bound L for R(k, l) usually requires exhibiting a red/green coloring of the complete graph KL−1 with no red Kk subgraph and no green Kl subgraph. Searching all colorings of a graph KL−1 becomes computationally extremely difficult as L increases; the number of colorings grows super-exponentially. So it is not easy to obtain the exact values of Ramsey numbers. The difficulty of computing Ramsey numbers was summed up quite nicely by the great Hungarian mathematician, Paul Erdo¨s: Suppose an evil spirit would tell us, “Unless you tell me the value of R(5, 5) I will exterminate the human race.” Our best strategy would perhaps be to get all the computers and computer scientists to work on it. If he would ask for R(6, 6) our best bet would perhaps be to try to destroy him before he destroys us [1]. Until now, there are only nine known nontrivial values for Ramsey numbers R(k, l) [7], see Table 1. It is a great challenge for mathematician and computer scientists to compute the exact values of Ramsey numbers. In this work, a new way is given for computing Ramsey numbers based on a kind of “chemical/biological” computational devices, instead of physical computational devices. Table 1. Known nontrivial values for R(k, l). k3 3 3 3 3 3 3 4 4 l3 4 5 6 7 8 9 4 5 R(k, l) 6 9 14 18 23 28 36 18 25 Membrane systems (usually called P systems) are a class of distributed parallel computing devices of a biochemical type, introduced in [3], which can be seen as a general computing architecture where various types of objects can be processed by various operations. The idea originates from the observation that certain processes which take place in the complex structure of living organisms can be considered as computations. We refer the reader to [5] for a motivation and detailed description of various P system models. In this work, P systems with active membranes are considered [4]. For a quick overview of P systems with active membranes, we refer the reader to Chapter 11 in [6]. In this work, an algorithm is presented in terms of P systems with active membranes to decide whether an integer number nis the value of Ramsey number R(k, l), whose computation time is polynomial with respect to n. If a lower bound Land an upper bound Uof a Ramsey number R(k, l) are known and the gap U−Lbetween the lower bound and upper bound is not big, then the value of Ramsey number R(k, l) can be obtained by running the above algorithm at most U−Ltimes. For example, 43 ≤R(5,5) ≤49, so it needs only to run the above algorithm at most 6 times in order to get the exact value of R(5,5). Hence, the algorithm given in this work looks attractive. January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 2. Computing Ramsey Numbers by P Systems Ramsey numbers R(k, l) (k, l ≥2) can be considered as a function from N2to N. The decision version of Ramsey number problem can be expressed as follows: given integers n, k, l, decide whether or not nis the value of Ramsey number R(k, l). The resolution of Ramsey number problem given below is a brute force algorithm, which consists of the following stages: •Generation Stage (I): Using membrane division for non-elementary membranes, all complete graphs Knwith different edge 2-colorings (say red and green) are produced. •Generation Stage (II): For each complete graph Knwith edges colored by red or green, all subsets of vertices are generated by using membrane division for non-elementary membranes. •Checking Stage (I): For each complete graph Knwith edges colored by red or green, we check whether there is a clique with kvertices and red edges. •Checking Stage (II): For each complete graph Knwith edges colored by red or green, if there is no clique with kvertices and red edges, then we check whether there is a clique with lvertices and green edges. •Output Stage: The system sends to the environment the right answer according to the results of the previous stage. If in all complete graphs Kn with edges colored by red or green, there is a clique with kvertices and red edges or a clique with lvertices and green edges, then the answer is yes. Otherwise, the answer is no. Let us consider the (polynomial time computable and bijective) function hn, k, li from N3onto N, where hn, k, li=hn, hk, lii, induced by hx, yi= ((x+l)(x+ y+ 1)/2) + x. For given n, k, l, a P system with active membranes Π(hn, k, li) is constructed to decide whether nis the value of Ramsey number R(k, l). Π(hn, k, li) = (O(hn, k, li), H, µ, w0, w1, w2, w3, w4, R),where O(hn, k, li) = {ai, ti, fi,¯ ti,¯ fi, f0 i,¯ f0 i, yi, zi,¯yi,¯zi|1≤i≤n} ∪ {gi|0≤i≤n+ 3} ∪{di|1≤i≤n(n−1) + 3} ∪ {hi, h0 i|0≤i≤max{k, l}} ∪ {ai,j |≤ i < j ≤n} ∪{ei,j,s |1≤i≤n+ 2,1≤j≤n+ 2,0≤s≤2l+ 7} ∪{¯ei,j,s |1≤i≤n+ 2,1≤j≤n+ 2,0≤s≤2n+ 2k+ 6} ∪{ci|0≤i≤n2+ 5n+ 2k+ 2l+ 26} ∪ {a, b, g, h, p, q, u, yes,no,no1,no2,no3}, H={0,1,2,3,4},µ= [[[[[ ]0 4]0 3]0 2]0 1]0 0,w0=c0,w1=w2=w3=λ,w4={{ai|1≤ i≤n}} ∪ {{ai,j |1≤i < j ≤n}} ∪ {{d1}}, and the set Rcontains the following rules (the use of these rules during the computations is also explained): (1) [ai,j]0 4→[ei,j,2l+7]+ 4[¯ei,j,2n+2k+6]− 4, 1 ≤i < j ≤n. (2) [[ ]+ i+1[ ]− i+1]0 i→[[ ]0 i+1]+ i[[ ]0 i+1]− i,i= 2,3. (3) [[ ]+ 2[ ]− 2]0 1→[[ ]0 2]0 1[[ ]0 2]0 1. The objects ai,j corresponds to edges (vi, vj), 1 ≤i < j ≤n. Using the rules of type (1), for non-deterministically chosen ai,j, two objects ei,j,2l+7 and ¯ei,j,2n+2k+6 are produced, placed in two separate copies of membrane 4, January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 where ei,j,2l+7 denotes that edge (vi, vj) is colored with red, and ¯ei,j,2n+2k+6 denotes that edge (vi, vj) is colored with green. The rules of types (2) and (3) are division rules for membrane with label 1, 2 and 3, to be used in steps which follow the use of the rules of type (1). The division of a membrane with label 4 is propagated from lower levels to upper levels of the membrane structure and the membranes are continuously divided. The membrane division stops at the level where the membrane has the label 1. During the division, the charge of the membranes with label 2, 3 and 4 first changes to positive or negative, then returns to neutral, hence the process can continue. In this way, in n(n−1) + 2 steps all 2n(n−1)/2graphs with different coloring of edges are generated, placed in 2n(n−1)/2separate copies of membrane 4. The structure of the system after n(n−1) + 2 steps is shown in Figure 1. 4 3 2 1 4 3 2 1 0 ⋯ Fig. 1. The structure of system after step n(n−1) + 2. (4) [di→di+1]α 4,α∈ {+,−,0}, 1 ≤i≤n(n−1) + 2. (5) [dn(n−1)+3]0 4→d1. At step n(n−1) + 3, the counter dn(n−1)+3 dissolves the membrane with label 4, and change to object d1. The object d1is used as a counter again in membranes with label 3. The computation passes to the next stage – for each graph with different coloring of edges, all subsets of vertices will be generated in order to check whether the corresponding graph has a clique Kkwith red edges or a clique Klwith green edges. (6) [ai]0 3→[ti]+ 3[fi]+ 3,1≤i≤n. (7) [[ ]+ 3[ ]− 3]0 2→[[ ]0 3]0 2[[ ]0 3]0 2. The objects aicorrespond to vertices vi, 1 ≤i≤n. Using the rules of type (6), for non-deterministically chosen ai, two objects tiand fiare produced, placed in two separate copies of membrane 3, where tidenotes that vertex viappears in some subset of vertices, and fidenotes that vertex vidoes not appear in some subset of vertices. The division rules of type (7) returns the charge of membranes with label 3 to neutral, so the process can continue. In 2nsteps, all 2nsubsets of the vertex set Vare generated for each graph. After step n2+n+ 3, the structure of the system is shown in Figure 2. (8) [di→di+1]0 3,1≤i≤n−1. (9) [dn→qqh0]0 3. At step n2+n, the subscript of the counter direaches n−1, and at step n2+n+2, objects qand h0are introduced; the objects qwill exit the membrane (at steps n2+n+ 4, n2+n+ 5), changing its polarization; the object h0is a new counter which will be used at the subsequent steps as shown below. January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 The next stage of the computation now starts – counting the number of objects ti(1 ≤i≤n) in each membrane with label 3, which corresponds to the cardinality of each subset; the subsets with cardinality exactly kwill be selected out. 3 2 1 0 ⋯ 3 2 ⋯ 3 2 1 ⋯ 3 2 Fig. 2. The structure of system after step n2+n+ 3. (10) [q]0 3→[ ]− 3u. (11) [q]− 3→[ ]0 3u. (12) [ti→¯ tiab]− 3, 1 ≤i≤n. (13) [fi→¯ fif0 i]− 3, 1 ≤i≤n. (14) [hi→h0 i]0 3, 0 ≤i≤k. (15) [h0 i→hi+1]+ 3, 0 ≤i≤k−1. (16) [a]0 3→[ ]+ 3u. (17) [b]+ 3→[ ]0 3u. At step n2+n+ 4, h0evolves to h0 0, and at the same time one copy of qexits the membrane, changing its polarization to negative, where the object uis a dummy object that will never evolve again. At step n2+n+ 5, tievolves to ¯ tiab,fievolves to ¯ fif0 i, and at the same time the other copy of qexits the membrane, changing its polarization to neutral. The objects ¯ tiand ¯ fihave the same meaning as objects tiand fi: the vertex viappear or doesn’t appear in some subset of vertices, respectively; they will be used in checking whether there is a copy of clique klwith red edges or green edges (the process will take place in membranes with label 2 as you will see below). At step n2+n+ 6, one copy of aexits the membrane, changing its polarization to positive. At step n2+n+ 7, h0 0evolves to h1, at the same time one copy of bexits the membrane, returning its polarization to neutral (this makes possible the use of rules of types (14) and (16)). The rules of types (14) – (17) are applied as many times as possible. Clearly, at step n2+n+ 5 + 2k, a membrane contains object hkif and only if the cardinality of the corresponding subset is at least k. At step n2+n+ 6 + 2k, in the membrane whose corresponding subset has cardinality more than k, hkevolves to h0 k, and one copy of achanges its polarization to positive. This membrane will no longer evolve, as no further rule can be applied to it. In the membrane whose corresponding subset has cardinality exactly k,hkevolves to h0 k, and its polarization remains neutral, because there is no copy of awhich can be used. The next stage of computation starts– checking whether a subset with cardinality kis a clique. (18) [h0 k→qqg]0 3. (19) [f0 i→yizi]− 3, 1 ≤i≤n. (20) [g→g0]− 3. (21) [¯ei,j,r →¯ei,j,r−1]α 3, 1 ≤i < j ≤n, 1 ≤r≤2n+ 2k+ 6, α∈ {+,−,0}. At step n2+n+ 7 + 2k, in the membranes with label 3 and polarization 0, h0 kevolves to qqg. At step n2+n+ 8 + 2k, one copy of qexits the membrane, changing its polarization to negative. At step n2+n+ 9 + 2k,fi(1 ≤i≤n) January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 evolves to yizi,gevolves to g0, and an object ¯ei,j,0appears for each edge (vi, vj) with green color (note that the objects ¯ei,j,2n+2k+6 are released from membranes with label 4 to membranes with label 3 at step n(n−1) + 3 by using the rule (5); from that time, the rules of type (21) start to work). At same time, the other copy of qexits the membrane, changing its polarization to neutral. (22) [yi→yi+1]0 3,1≤i≤n−1.(23) [zi→zi+1]0 3,1≤i≤n−1. (24) [¯ei,j,0→¯es(i),s(j),0]0 3,1≤i < j ≤n+ 1,where s(t) = min(t+ 1, n + 2). (25) [gi→gi+1]0 3, 1 ≤i≤n−1.(26) [zn→p]0 3.(27) [yn]0 3→[ ]+ 3u. At step n2+n+2k+10, yi, zi(1 ≤i≤n−1) evolve to yi+1, zi+1,znevolves to p, ¯ei,j,0(1 ≤i < j ≤n) evolve to ¯es(i),s(j),0, where s(t) = min(t+ 1, n + 2); at same time, ynexits the membrane where it appears, changing the polarization of that membrane to positive. (28) [¯ei,n+1,0→u]+ 3,1≤i≤n. (29) [p]+ 3→[ ]0 3u. In the membranes with label 3 and positive polarization (i.e., the membranes where ynappear in the last step, which means that vertex vndoes not belong to the corresponding subset), ¯ei,n+1,0(1 ≤i≤n) evolve to u; at the same time, object pexits the membrane, returning the polarization of the membrane to neutral (this makes possible the use of rules of types (22)–(27)). In the membranes with label 3 and neutral polarization (i.e., the membranes where yndo not appear in the last step, which means that vertex vnbelongs to the corresponding subset), using rule of type (24), ¯ei,n+1,0(1 ≤i≤n) evolve to ¯ei+1,n+2,0(that is, the edge (vi, vn) with green color does not belong to V×(V−A)∪(V−A)×V, where Ais the corresponding subset). The rules of types (22)–(29) are applied as many times as possible. After 2n steps, a membrane contains an object ¯en+2,n+2,0if and only if that membrane contains a green edge which does not belong to V×(V−A)∪(V−A)×V, where Ais the corresponding subset. If the object ¯en+2,n+2,0does not appear in a membrane with label 3 (that is, the corresponding subset of vertices is a clique with kvertices and red edges), the object yes will appear, and it eventually exits membrane with label 1. If the object ¯en+2,n+2,0appears in a membrane with label 3 (that is, the corresponding subset of vertices is not a clique with kvertices and red edges), this membrane is dissolved by the rule (33), release its content to immediately outside membrane with label 2, and the computation passes to the next stage – checking whether there exists a clique with lvertices and green edges. (30) [gn→gn+1q]0 3. (31) [gn+1 →gn+2]0 3. (32) [gn+2 →gn+3]− 3. (33) [¯en+2,n+2,0]− 3→h. (34) [gn+3]− 3→[ ]− 3yes. (35) [yes]0 2→[ ]0 2yes. (36) [yes]0 1→[ ]+ 1u. At step n2+3n+2k+10, the object gnevolves to gn+1q. At step n2+3n+2k+11, the object gn+1 evolves to gn+2q, and object qexits the membrane, changing the polarization to negative (using rule of type (10)). At step n2+3n+2k+12, January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 in the membranes which contain object ¯en+2,n+2,0,gn+2 evolves to gn+3, and ¯en+2,n+2,0dissolves the membrane with label 3. In the next step, the next stage of computation starts – checking whether there exists a clique with l vertices and green edges. At step n2+ 3n+ 2k+ 12, in the membranes which do not contain object ¯en+2,n+2,0,gn+2 evolves to gn+3, the membranes with label 3 are not dissolved and the polarization remains negative, in the next step they produce the object yes. After two more steps, the object yes changes the polarization of membrane with label 1 to positive, telling us that the associated complete graph with the membrane labeled by 1 has a clique with kvertices and red edges; after that, this membrane with label 1 will not send out objects to membrane with label 0 any more. (37) [h→qqh0]0 2. At step n2+ 3n+ 2k+ 13, object hevolves to qqh0, where qis used to change the polarization, and h0is used to count the cardinality of subsets of vertices. (38) [q]0 2→[ ]− 2u. (39) [q]− 2→[ ]0 2u. (40) [¯ ti→ab]− 2, 1 ≤i≤n. (41) [ ¯ fi→¯ f0 i]− 2, 1 ≤i≤n. (42) [hi→h0 i]0 2, 0 ≤i≤l. (43) [h0 i→hi+1]+ 2, 0 ≤i≤l−1. (44) [a]0 2→[ ]+ 2u. (45) [b]+ 2→[ ]0 2u. As the rules of type (10)–(17), the rules of type (38)–(45) are used to check whether the cardinality of the corresponding subset of vertices in each elementary membrane with label 2 equals to l. Note that the membranes with label 2 containing membrane with label 3 will not evolve anymore, their corresponding subsets of vertices induce cliques with kvertices and red edges. (46) [h0 l→qqg]0 2. (47) [ ¯ f0 i→¯yi¯zi]− 2, 1 ≤i≤n. (48) [g→g0]− 2. (49) [ei,j,r →ei,j,r−1]α 2, 1 ≤i < j ≤n, 1 ≤r≤2l+ 7, α∈ {+,−,0}. At step n2+3n+2k+2l+17, in the membranes with label 2 and polarization 0, h0 levolves to qqg. At step n2+3n+2k+2l+18, one copy of qexits the membrane, changing its polarization to negative. In the next step, ¯ f0 i(1 ≤i≤n) evolves to ¯yi¯zi,gevolves to g0,ei,j,0appears for each edge (vi, vj) with red color, and the other copy of qexits the membrane, changing its polarization to neutral. (50) [¯yi→¯yi+1]0 2,1≤i≤n−1.(51) [¯zi→¯zi+1]0 2,1≤i≤n−1. (52) [ei,j,0→es(i),s(j),0]0 2,1≤i < j ≤n+ 1,where s(t) = min(t+ 1, n + 2). (53) [gi→gi+1]0 2, 1 ≤i≤n−1.(54) [¯zn→p]0 2.(55) [¯yn]0 2→[ ]+ 2u. At step n2+3n+2k+2l+20, ¯yi,¯zi(1 ≤i≤n−1) evolve to ¯yi+1,¯zi+1, ¯znevolves to p,ei,j,0(1 ≤i < j ≤n) evolve to es(i),s(j),0, where s(t) = min(t+1, n+2); at same time, ¯ynexits the membrane where it appears, changing the polarization of that membrane to positive. (56) [ei,n+1,0→u]+ 2,1≤i≤n. (57) [p]+ 2→[ ]0 2u. The rules of type (50)–(57) are used to check whether a subset of vertices with lvertices induces a clique with green edges. In 2nsteps a membrane contains an object en+2,n+2,0if and only if that membrane contains a red edge which does not belong to V×(V−A)∪(V−A)×V, where Ais the corresponding subset. This process finishes after step n2+ 5n+ 2k+ 2l+ 19. January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 (58) [gn→gn+1q]0 2. (59) [gn+1 →gn+2]0 2. (60) [gn+2 →gn+3]− 2. (61) [gn+3]− 2→[ ]− 2yes. (62) [yes]0 1→[ ]+ 1u. (63) [en+2,n+2,0]− 2→[ ]+ 2no1. (64) [no1→no2]0 1. (65) [no2→no3]0 1. (66) [no3]0 1→[ ]+ 1no. At step n2+ 5n+ 2k+ 2l+ 20, gnevolves to gn+1q. In the next step, gn+1 evolves to gn+2q, and object qexits the membrane, changing the polarization to negative. At step n2+ 5n+ 2k+ 2l+ 22, in the membranes with label 2 which do not contain object en+2,n+2,0,gn+2 evolves to gn+3, and the polarization remains negative, in the next step they produce the object yes. At step n2+ 5n+ 2k+ 2l+ 24, the object yes exits membrane with label 1 changing the polarization to positive, telling us that the associated complete graph with the membrane with label 1 has a clique with lvertices and green edges. At step n2+5n+2k+2l+22, in the membranes with label 2 which contain object en+2,n+2,0,gn+2 evolves to gn+3, and en+2,n+2,0exit these membranes, changing the polarization of these membranes to positive (the other copies of en+2,n+2,0cannot exit any more). After two more steps, no1evolves to no3. At step n2+ 5n+ 2k+ 2l+ 25, if the polarization of a membrane with label 1 is still neutral, then it means that the associated graph with the membrane with label 1 has neither a clique with kvertices and red edges nor a clique with l vertices and green edges. The object no3exits, evolving to no, also changing the polarization of membrane with label 1 to positive (in order that the objects no remaining in it cannot continue to exit). (67) [no]0 0→[ ]+ 0no. (68) [ci→ci+1]0 0, 0 ≤i≤n2+ 5n+ 2k+ 2l+ 25. (69) [cn2+5n+2k+2l+26]0 0→[ ]0 0yes. If the object no appears in the skin membrane labeled by 0, then at step n2+ 5n+ 2k+ 2l+ 26, it is send out to the environment, telling us that there exists a complete graph with nvertices and edges colored by red and green that contains neither a clique with kvertices and red edges nor a clique with lvertices and green edges; the computation stops. Note that if there is no object no in the skin membrane, then it means that each complete graph with nvertices and edges colored by red and green contains a clique with k vertices and red edges or a clique with lvertices and green edges, and at step n2+ 5n+ 2k+ 2l+ 26 the polarization of the skin membrane is neutral. The object cn2+5n+2k+2l+25 (originating from c0) evolves to cn2+5n+2k+2l+26, and in the next step, cn2+5n+2k+2l+26 exits the skin membrane, evolving to the object yes; the computation stops. From the previous explanation of the use of rules, one can easily see how this P system works. It is clear that the object yes exits the system if only if the integer n is the value of Ramsey number R(k, l). If nis not the value of R(k, l), then at step n2+ 5n+ 2k+ 2l+ 26 the system sends the object no to the environment. The formal verification of the above computation is omitted, just pointing out that the construction of the above P system can be done in polynomial time by a January 13, 2011 14:15 WSPC/INSTRUCTION FILE S0129054111007800 deterministic Turing machine. Because the sets of rules associated with the system Π(hn, k, li) are recursive, it is enough to note that the amount of necessary resources for defining such system is polynomial with respect to n: •Size of the alphabet: (n+ 2)2(2n+ 2k+ 2l+ 13) + 2n2+n(n−1)/2 + 16n+ 2k+ 2l+ 2 max{k, l}+ 44 ∈O(n3); •Initial number of cells: 5 ∈O(1); •Initial number of objects: n(n+ 1)/2 + 2 ∈O(n2); •Number of rules: n(n−1)(2n+2k+6)+n(n+1)(2l+7)+4n2+17n+4k+4l+70 ∈ O(n3); •Maximal length of a rule: 7 ∈O(1). 3. Discussion Because it is very hard to get the exact values of Ramsey numbers, this is a good way for examining the power of unconventional computing models. In this work, an algorithm is presented in the framework of P systems to decide whether an integer number nis the value of Ramsey number R(k, l), whose computation time is polynomial with respect to n. Even for small kand l, e.g., the case for R(5,5) and R(6,6), it is still very difficult to obtain the values of Ramsey numbers. But “biochemical computers” or “artificial cells” seem very suitable for computing Ramsey numbers. The Ramsey number R(5,5) has the bounds 43 ≤R(5,5) ≤49 [7]. The value of R(5,5) can be obtained after running our algorithm at most 6 times, one time for each integer from 43 to 48. In each running of algorithm, the number of biochemical steps is not more than 2591 (computation steps n2+5n+2k+2l+27 ≤482+5×48+2×5+2×5+27 = 2591). In general, there are a lower and upper bound of Ramsey number R(k, l) 2m≤R(k, l)≤k+l−2 l−1, where m= min{k, l}. In order to obtain the exact value of Ramsey number R(k, l), the algorithm has to be run for each integer between the bounds of R(k, l). When k, l are large integers and k >> l, the gap between the upper bound and the lower bound can be very big. In these cases, the algorithm given in this work is not efficient enough to obtain the value of Ramsey number R(k, l). It remains open to design a P system such that the system outputs the value of Ramsey number R(k, l) in a polynomial steps after the integers k, l are inputted into the system. Although the algorithm presented in this work seems attractive from the theoretical point of view, the following analysis shows that it is not realistic. The algorithm is a brute force one, which tests all possible colorings of Knfor a recommended n. As shown in the above section, the amount of resources to construct the P system is O(n3). But, during the computation, the P system generates 2n(n−1)/2 separate copies of membrane 4. This cannot happen in this universe for an integer n, 43 ≤n≤49. (One can imagine how big such space size is. The human being brain