An efficient time-free solution to SAT problem by P systems with proteins on membranes

An efficient time-free solution to SAT problem by P systems with proteins on membranes Bosheng Song a, Mario J. Pérez-Jiménez b, Linqiang Pan a,∗ a Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China b Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain a b s t r a c t Keywords: P system Membrane protein Time-free uniform solution SAT P systems with proteins on membranes are a class of bio-inspired computing models, where the execution of each rule completes in exactly one time unit. However, in living cells, the execution time of biochemical reactions is difficult to know precisely because of various uncontrollable factors. In this work, we present a time-free uniform solution to SAT problem by P systems with proteins on membranes in the sense that the correctness of the solution is irrelevant to the times associated with the involved rules, and the P systems are constructed from the sizes of instances. 1. Introduction Membrane computing is an active branch of natural computing, which is inspired by the structure and the functioning of living cells, abstracting computational ideas (e.g., computational models, data structure, data operation) from the way in which chemicals interact and cross cellular membranes. This computational model was initiated by Gh. P˘ aun at the end of 1998 [15] and it has received great attention from computer scientists, biologists, formal linguists and complexity theoreticians. The computational models considered in the framework of membrane computing are called P systems, which are parallel and distributed computational models. In general, three main types of P systems have been considered until now: cell-like P systems, which have a hierarchical arrangement of membranes delimiting compartments where multisets of chemicals (called objects) evolve according to given evolution rules [1,15,24]; tissue-like P systems, which have arbitrary graphs as underlying structures, with cells placed in the nodes while edges correspond to communication channels [3,8,9]; neural-like P systems, which are motivated by the neurophysiological behavior of neurons sending electrical impulses (spikes) along axons to other neurons [6,10,21]. A recent coverage of membrane computing can be found in [17], and for the most up-to-date information in this area, please refer to the P systems webpage: http://ppage.psystems.eu. The present work deals with cell-like P systems with proteins on membranes (in what follows, when we say P systems with proteins on membranes, it means cell-like P systems with proteins on membranes), which can be viewed as a model combining membrane systems and brane calculi as introduced in [12]. P systems with proteins on membranes can have objects both in compartments/regions, as usual in P systems, and also on membranes (called proteins). In such P systems, *Corresponding author. E-mail address: [email protected] (L. Pan). the proteins (which are always placed on the membranes) are used mainly to control the evolution of other objects. The evolution rules used in P systems with proteins on membranes are inspired by the symport/antiport rules [11], but the objects can evolve under the control of proteins placed on membranes (the protein can also change). Moreover, P systems with proteins on membranes deal with only one protein, one object inside the region and/or one object outside of it. P systems with proteins on membranes were proved to be universal by combining several various types of rules [7,12, 14]. If we allow membrane division rules in this kind of P systems, then it can solve the computationally hard problems efficiently. In [13], the SAT problem was solved by a uniform family of P systems with proteins on membranes and membrane division in a polynomial time. Recently, P systems with proteins on membranes were used to characterize PSPACE-complete problem, that is, the polynomial complexity class (semi-uniform version) associated with recognizer P systems with proteins on membranes coincides with the class of PSPACE-complete problems [27]. In the semantics of P systems with proteins on membranes, a global clock is assumed, marking time units for the whole system, all the rules are applied synchronously and the execution of each rule takes exactly one time unit (one step). Actually, in cell biology, different biochemical reactions may take different times to be completed because they are influenced by various uncontrollable factors, such as biological signals, catalyst, and medium temperature. Thus, the assumption that the execution of each rule takes exactly one time unit is not in conformity with the biological reality. With this biological motivation, time-free P systems were formulated in [2], where such P systems generate (or accept) the same family of vectors of natural numbers, independent from the value assigned to the execution time of each rule, and by simulating non-synchronized P systems, time-free P systems were proved to be universal. Time-free solutions to computational hard problems as open problems were formulated in [5]. In [19], a family of P systems with active membranes was designed for a time-free solution to SAT problem in the sense that the correctness of the solution is irrelevant to the execution time used by the involved rules. Since then, several variants of P systems were also considered to time-freely solve NP-complete problems [20,23,25,26]. In this work, we focus on timed P systems with proteins on membranes, and a time-free uniform solution to the SAT problem by using such systems is present, where the correctness of the solution is irrelevant to the execution time used by the involved rules, and the P systems are constructed from the sizes of instances. 2. P systems with proteins on membranes 2.1. Preliminaries In this subsection, we only introduce a few basic notions and notations from formal languages theory that will be used in what follows, the reader can refer to [18] for more details. An alphabet is a non-empty set and its elements are called symbols. A string u over is a finite sequence of symbols from . The number of occurrences in uof symbols from is called the length of the string u, denoted by |u|. By |u|a we denote the number of occurrences of symbol ain u. As usual, the empty string (with length 0) will be denoted by λ. The set of all strings over an alphabet is denoted by ∗and by +=∗\{λ}we denote the set of non-empty strings. Alanguage over is a set of strings over . For an alphabet , a multiset over is a pair (, f)where f:→Nis a mapping, Nis the set of natural numbers. If m =(, f)is a multiset, then its support is defined as supp(m) ={x ∈| f(x) >0}. If supp(m) ={a1, ..., ak}then we denote m ={af(a1) 1, ..., af(ak) k}. A multiset is finite if its support is a finite set. We denote by ∅the empty multiset. We also represent a multiset mover Vas a string w ∈V∗such that |w|ai=m(ai), 1 ≤i ≤n. All permutations of this string identify the same multiset mprecisely. In what follows, we will not distinguish between the representation of multiset in mapping form or string form. If m1=(, f1), m2=(, f2)are multisets over , then the union of m1and m2, denoted by m1+m2, is the multiset (, g), where g(x) =f1(x) +f2(x)for each x ∈; the relative complement of m2in m1, denoted by m1\m2, is the multiset (, g), where g(x) =f1(x) −f2(x)if f1(x) ≥f2(x), and g(x) =0otherwise. 2.2. P systems with proteins on membranes and membrane division In this subsection, we first introduce the notion of P systems with proteins on membranes and membrane division from [12], then the definition of recognizer P systems with proteins on membranes is given. In this work, we consider P systems with two types of symbols: proteins and objects. Proteins are placed on the membranes, which never leave their places during the evolution process (but they can evolve) and are used mainly to control the evolution of other objects, and the usual objects are placed in the regions delimited by membranes, which can leave the regions for the neighboring regions during the evolution. If a protein pis placed on a membrane (with label) iand an object ais placed in the region delimited by that membrane, it is denoted by [ p |a]i. The regions of a membrane structure and the membranes themselves can contain multisets of objects and of proteins, respectively. There are several types of rules for handling the proteins and the objects, in this work we consider the types of rules introduced in [12]. P systems can be used for solving decision problems by using the trade-off space for time. A P system solving such a problem demands that an exponential workspace can be generated in a polynomial (or linear) time, and membrane division rules can generate that workspace. This kind of rules can be introduced in membranes controlled by proteins on them in such manner that proteins will trigger these rules. Definition 1. A P system with proteins on membranes and membrane division of degree m ≥1is a tuple  = (O, P, μ, w1/z1, ..., wm/zm, E, R1, ..., Rm, iout), where: •Oand Pare finite non-empty alphabets such that O ∩P=∅; •μis a rooted tree with mnodes labeled by 1, ..., m; •wi, 1 ≤i ≤m, are multisets over O; •zi, 1 ≤i ≤m, are multisets over P; •E⊆Ois a finite alphabet; •Ri, 1 ≤i ≤m, are finite sets of rules of the following types: –Evolution rules of the types: (a)[ p |a]i→[ p|b ]i, (b)a [ p |] i→b [ p|] i, (c)[ p |a]i→b [ p|] i, (d)a [ p |] i→[ p|b]i, (e)a [ p |b]i→c[ p|d]i, where p, p∈P, a, b, c, d ∈Oand 1 ≤i ≤m. –Division rules of the type [ p |] i→[ p|] i[ p |] i, where p, p, p ∈P, 1 ≤i ≤m, i = iout, and icannot be the root of the tree μ; •iout ∈{0, 1, ..., m}. A P system with proteins on membranes and membrane division of degree m ≥1can be viewed as a set of mmembranes, labeled by 1, ..., m, each of them delimiting regions (the space between a membrane and the immediately inner membranes) such that: (a) w1, ..., wmrepresent the finite multisets of objects (symbols of the alphabet O) initially placed in the mmembranes of the system; (b) z1, ..., zmrepresent the finite multisets of proteins (symbols of the alphabet P) initially placed on the mmembranes of the system; (c) Eis the set of objects initially located in the environment of the system, all of them available in an arbitrary number of copies; and (d) iout represents a distinguished zone which will encode the output of the system. We use the term zone i(0 ≤i ≤m) to refer to membrane iin the case 1 ≤i ≤mand to refer to the environment in the case i =0. The length of an evolution rule is the total number of proteins and objects involved in that rule. A configuration of a P system with proteins on membranes and membrane division is described by the current membrane structure, together with all multisets of objects located in its regions, and multisets of proteins present on membranes. The initial configuration is given by (w1/z1, ..., wm/zm, μ), that is, by the multisets of objects w1, ..., wmplaced in the membranes, the multisets of proteins z1, ..., zmplaced on the membranes and the initial membrane structure. An evolution rule [ p |a]i→[ p|b]iis applicable to a configuration if membrane ibelongs to that configuration, the object ais placed in membrane iand the protein pis placed on that membrane. When applying such a rule, in reaction with an object aand a protein p, in the membrane i, the object ais replaced by object band the protein pis replaced by protein p. An evolution rule a [ p |] i→b [ p|] iapplicable to a configuration if membrane ibelongs to that configuration, the object ais placed in the father of membrane i(the environment in the case of membrane iis the root) and the protein pis placed on that membrane. When applying such a rule, in reaction with an object aand a protein p, in the father of the membrane i, the object ais replaced by object band on the membrane i, the protein pis replaced by protein p. An evolution rule [ p |a]i→b [ p|] iapplicable to a configuration if membrane ibelongs to that configuration, the object a is placed in the membrane iand the protein pis placed on that membrane. When applying such a rule, in reaction with an object aand a protein p, in the father of the membrane i, the object ais replaced by object band on the membrane i, the protein pis replaced by protein p. In a similar way is defined the semantics of the remaining rules. A division rule [ p |] i→[ p|] i[ p |] iis applicable to a configuration if membrane ibelongs to that configuration, if the protein pis placed on membrane i. When applying such a rule, in reaction with the protein p, membrane iis divided into two membranes with the same label i; in the first copy, the protein pis replaced by protein p, in the second one, the protein pis replaced by protein p; all the other objects in membrane iand all the other proteins on membrane i are replicated, and the copies of them are placed in and on the two new membranes, respectively. If iout ∈{1, ..., m}, then membrane iout cannot be divided. The root of the membrane structure cannot be divided. The rules in a system are used in a non-deterministic maximally parallel manner as customary in membrane computing. At each step, all membranes which can evolve must evolve in a maximally parallel way (at each step we apply a multiset of rules which is maximal, no further rule can be added being applicable). This way of applying rules has only one restriction: when a membrane is divided, the division rule is the only one which is applied for that membrane at that step; thus, the proteins and objects in that membrane do not evolve by means of evolution rules. The new membranes resulting from division could participate in the interaction with other membranes or the environment by means of evolution rules at the next step, providing that they are not divided once again. The label of a membrane identifies the rules which can be applied to it precisely. The system passes from one configuration to another one by a maximally parallel application of rules as described above. A computation is a (finite or infinite) sequence of configurations such that: the first term of the sequence is the initial configuration of the system; each non-initial configuration of the sequence is obtained from the previous configuration by applying rules of the system in a maximally parallel manner with the restrictions previously mentioned; if the sequence is finite (called halting computation), then the last term of the sequence is a halting configuration. All the computations start from an initial configuration and proceed as stated above; only a halting computation gives a result, which is encoded by the objects present in the output zone iout in the halting configuration. Definition 2. A recognizer P system with proteins on membranes of degree m ≥1is a tuple  =(O, P, , μ, w1/z1, ..., wm/zm, E, R1, ..., Rm, iout, iin)such that: •The tuple (O, P, μ, w1/z1, ..., wm/zm, E, R1, ..., Rm, iout), is a P system with proteins on membranes of degree m such that the output zone is the environment (iout =0)and in this case, iout is usually omitted from the tuple; •is an (input) alphabet strictly contained in Osuch that E∩=∅; •The initial multisets w1, ..., wmare over O \; •iin ∈{1, ..., m}is the label of a distinguished (input) membrane; •The working alphabet contains two distinguished elements yes and no; •All the computations halt; •If Cis a computation of the system, then either object yes or object no (but not both) must appear in the environment when the system halts. For recognizer P systems with proteins on membranes, we say that a computation is an accepting computation (resp., rejecting computation) if the object yes (resp., no) appears in the environment associated with the corresponding halting configuration. For each multiset wover the input alphabet , the computation of the system with input w starts from the configuration of the form (w1/z1,...,(wiin +w)/ziin ,...,wm/zm,μ), that is, the input multiset whas been added to the contents of the input membrane iin. Therefore, we have an initial configuration associated with each input multiset w(over the input alphabet ) in this kind of systems. We denote by CPE(k)the class of recognizer P systems with proteins on membranes with the length of evolution rules at most k. 2.3. Recognizer timed P systems with proteins on membranes In this subsection, we first give the definition of timed P systems with proteins on membranes, and then introduce the notion of recognizer timed P systems with proteins on membranes. Definition 3. A timed P system with proteins on membranes of degree m ≥1is a pair (, e), where is a P system with proteins on membranes of degree m, and eis a computable time-mapping of , that is, eis a mapping from the finite set of rules R1∪···∪Rminto the set of natural numbers N. For each rule r, the natural number e(r)represents the execution time of rule r. We denote by (e)the timed P system with proteins on membranes (, e). A timed P system with proteins on membranes (e)works in the following way: an external clock is assumed, which marks time-units of equal length, starting from instant 0. According to this clock, the step tof a computation is defined by the period of time between instant t−1 and instant t. If a membrane icontains a rule r(evolution rule or division rule) selected to be executed, then the execution of such rule takes e(r)time units to complete. Therefore, if the execution of a rule ris started at instant j, then the execution is completed at instant j +e(r)and the resulting objects, protein and membranes generated by the division rule become available only at the beginning of step j +e(r) +1. If an evolution rule is started, then the occurrences of objects and protein subject to this rule cannot be subject to other rules until the implementation of the rule completes; if the division rule is started, then the occurrences of protein and membrane subject to this rule cannot be subject to other rules until the implementation of the rule completes. Definition 4. A recognizer timed P system with proteins on membranes of degree m ≥1is a tuple (, e), where is a recognizer P system with proteins on membranes of degree mand eis a computable time-mapping of . 2.4. Time-free uniform solutions to decision problems by recognizer P systems with proteins on membranes In a timed P systems with proteins on membranes, we use the rule starting step (RS-step, for short) to define the computation step, which was proposed in [19]. Definition 5. In timed P systems with proteins on membranes, a computation step is called an RS-step if at this step at least one rule starts its execution, that is, steps in which some objects and proteins “start” to evolve or membranes “start” to divide. Let us recall that a decision problem, X, is a pair (IX, θX) such that IXis a language over a finite alphabet (whose elements are called instances) and θXis a total Boolean function (that is, predicate) over IX. Definition 6. We say that a decision problem X=(IX, θX)is solvable in polynomial RS-steps by a family ={n|n ∈N} of recognizer P systems with proteins on membranes in a time-free manner, if the following holds: •the family is polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system nfrom n ∈N. •there exists a pair (cod, s)of polynomial-time computable functions over IXsuch that: –for each instance u ∈IX, s(u)is a natural number and cod(u)is an input multiset of the system s(u). –the family is time-free sound with respect to (X, cod, s); that is, for any time-mapping e, the following property holds: for each instance of the problem u ∈IXsuch that there exists an accepting computation of s(u)(e)with input cod(u), we have X(u) =1. –the family is time-free complete with respect to (X, cod, s); that is, for any time-mapping e, the following property holds: for each instance of the problem u ∈IXsuch that X(u) =1, every computation of s(u)(e)with input cod(u) is an accepting computation. –the family is time-free polynomially bounded with respect to (X, cod, s); that is, there exists a polynomial function p(n)such that for any time-mapping eand for each u ∈IX, all the computations in s(u)(e)with input cod(u)halt in, at most, p(|u|)RS-steps. We also say that the family provides an efficient time-free solution to the decision problem X. We denote by PMCtf CPE(k) the family of problems that can be solved by recognizer P systems with proteins on membranes and the length of evolution rules at most kin a time-free manner. 3. A time-free uniform solution to SAT problem by using recognizer P systems with proteins on membranes The SAT problem is the best known NP-complete problem [4], which is defined as follows: Given a Boolean formula in conjunctive normal form (CNF), determine whether or not it is satisfiable, that is, whether there exists an assignment to its variables on which it evaluates to be true. The following theorem provides a polynomial RS-steps solution to the SAT problem by a family of P systems with proteins on membranes in a time-free uniform manner. Theorem 3.1. The SAT problem can be solved in polynomial RS-steps by a family of P systems with proteins on membranes in a time-free uniform manner, where the length of evolution rules is at most 6. Proof. Consider a propositional formula ϕ=C1∧C2∧···∧Cm, with Ci=yi,1∨···∨ yi,pi, for some m ≥1, pi≥1, and yi,j∈{xk, ¬xk|1 ≤k ≤n}, for each 1 ≤i ≤m, 1 ≤j ≤pi, where ¬xkis the negation of a propositional variable xk, the two connections ∨, ∧are or, and, respectively. Let us consider the polynomial time computable function m, n =((m +n)(m +n +1)/2) +m. It is primitive recursive and bijective from N2onto N. In what follows, we construct a family ={t|t∈N}, such that giving the appropriate input multisets, each system twill solve all instances of SAT with nvariables and mclauses, where t=m, n. We use the following notations to encode a propositional formula ϕ: cod(ϕ)=α1,1...α1,nα2,1...α2,n......αm,1...αm,n, where for 1 ≤i ≤m, 1 ≤j ≤nwe have: αi,j=⎧ ⎪ ⎨ ⎪ ⎩ bi,jif xjappears in Ci; b i,jif ¬xjappears in Ci; b i,jif xjand ¬xjdo not appear in Ci. For each m, n ∈N, we construct the recognizer P system with proteins on membranes m,n=(O,P,,μ,w1/z1,...,w4/z4,∅,R1,...,R4,iin), with the following components: •O =∪{aj, a(1) j, a(2) j, a(3) j, tj, fj|1 ≤i ≤n} ∪{di|1 ≤i ≤m} ∪{an+1, c, yes, no}is the set of objects, •P={p+ j, p− j, qj, q j, rm+1,j|1 ≤j ≤n} ∪{pk|1 ≤k ≤n +m +1} ∪{ri,j|1 ≤i ≤m, 1 ≤j ≤n} ∪{r1,n+1, qn+1, s, s, s}is the set of proteins, •={bi,j, b i,j, b i,j|1 ≤i ≤m, 1 ≤j ≤n}is the input alphabet, •μ =[ [ [ ]3]2[ ]4]1is the initial membrane structure, •w1=no, w2=a1, w3=λand w4=λare the initial multisets contained in membranes, •z1=s, z2=p1, z3=r1,1, z4=q1are the initial proteins placed on membranes 1, 2, 3, 4, respectively, •iin =3is the input membrane, and R =1≤i≤4Riis a finite set of rules of the following: G1,j:[ pj|] 2→[ p+ j|] 2[ p− j|] 2, 1 ≤j ≤n. G2,j:[ p+ j|aj]2→[ p+ j|tj]2, 1 ≤j ≤n. G3,j:[ p− j|aj]2→[ p− j|fj]2, 1 ≤j ≤n. G4,i,j:{tj[ri,j|bi,j]3→di[ri+1,j|tj]3, tj[ri,j|b i,j]3→c[ri+1,j|tj]3, tj[ri,j|b i,j]3→c[ri+1,j|tj]3|1≤i≤m,1≤j≤n}. G5,i,j:{fj[ri,j|bi,j]3→c[ri+1,j|fj]3, fj[ri,j|b i,j]3→di[ri+1,j|fj]3, fj[ri,j|b i,j]3→c[ri+1,j|fj]3|1≤i≤m,1≤j≤n}. G6,i,j:[ ri,j|tj]3→tj[ ri,j|] 3, 2 ≤i ≤m, 1 ≤j ≤n. G7,i,j:[ ri,j|fj]3→fj[ ri,j|] 3, 2 ≤i ≤m, 1 ≤j ≤n. G8,j:[ rm+1,j|tj]3→a(1) j[ r1,j+1|] 3, 1 ≤j ≤n. G9,j:[ rm+1,j|fj]3→a(2) j[ r1,j+1|] 3, 1 ≤j ≤n. G10,j:[ p+ j|a(1) j]2→a(1) j[ p− j|] 2, 1 ≤j ≤n. G11,j:[ p− j|a(2) j]2→a(2) j[ p+ j|] 2, 1 ≤j ≤n. G12,j:a(2) j[ p− j|] 2→[ p− j|a(3) j]2, 1 ≤j ≤n. G13,j:[ p− j|a(3) j]2→a(3) j[ p+ j|] 2, 1 ≤j ≤n. G14,j:a(3) j[ qj|] 4→[ q j|aj+1]4, 1 ≤j ≤n. G15,j:[ q j|] 4→[ qj+1|] 4[ qj+1|] 4, 1 ≤j ≤n. G16,j:[ qj|aj]4→aj[ qj|] 4, 2 ≤j ≤n +1. G17,j:aj+1[ p+ j|] 2→[ pj+1|aj+1]2, 1 ≤j ≤n. C1,i:[ pn+i|di]2→di[ pn+i+1|] 2, 1 ≤i ≤m. O1:[ pn+m+1|an+1]2→yes[ pn+m+1|] 2. O2:[ s|yes ]1→yes[ s |] 1. O3:no[ s |] 1→[ s |no ]1. O4:[ s |no ]1→no[ s|] 1. In what follows, we give the overview of a computation to show how the propositional formula ϕwith nvariables and mclauses is solved by the system m,nwith input cod(ϕ). The solution is proposed via a brute force algorithm, which consists in the following phases. •Generation phase: the membrane with label 2 is divided for ntime, all truth-assignments for the nvariables are produced, and the clauses which are satisfiable by the corresponding truth-assignment are checked. •Checking phase: checking whether there is a truth-assignment that makes the boolean formula evaluate to be true. •Output phase: the system sends the right answer to the environment according to the results of the previous phase. Let ebe any time-mapping from Rto N, which represents the execution times for the rules from R. In what follows, we will check how the above constructed system works in each phase. Generation phase. In the initial configuration of the system, we have object no in membrane 1 and protein son membrane 1, object a1in membrane 2 and protein p1on membrane 2, input multiset cod(ϕ)in membrane 3 and protein r1,1on membrane 3, and protein q1is placed on membrane 4, where there is no object initially. At step 1, under the influence of the protein p1on membrane 2, division rule G1,1is applied, membrane 2 is divided into two copies of membrane 2, with the protein p1replaced by p+ 1and p− 1, respectively. For any given time-mapping e, the execution of rule G1,1completes in e(G1,1)steps. At step 1, except for the application of rule G1,1, under the influence of the protein son membrane 1, the application of rule O4also starts; and from step 2 to step e(G1,1), there is no rule starting. So, during the execution of rule G1,1(i.e., from step 1 to step e(G1,1)), there is one RS-step. Note that the number of RS-steps during the execution of rule G1,1is independent on the time-mapping e. With the proteins p+ 1and p− 1present on two separate copies of membrane 2, rules G2,1and G3,1are enabled and applied at the same step, but the executions of rules G2,1and G3,1may complete at different steps due to the fact that the execution time associated with rules G2,1and G3,1can be different. By applying the rule G2,1, the object a1evolves to t1 (representing the truth value true); by using the rule G3,1, the object a1evolves to f1(representing the truth value false). When the object t1(resp. f1) appears in membrane 2, and the protein r1,1placed on membrane 3, one of rules in G4,1,1 (resp. G5,1,1) is enabled, which corresponds to check whether the first clause is satisfied by the truth-assignment true (resp. false) of variable x1. By using one of rules in G4,1,1(resp. G5,1,1), the object d1appears in membrane 2 only when the object b1,1(resp. b 1,1) is present in membrane 3; meanwhile, the protein r1,1placed on membrane 3 is changed to r2,1. If membrane 3 contains the object b 1,1or b 1,1(resp. b1,1or b 1,1), one copy of the object cwill appear in membrane 2, and the protein placed on membrane 3 changed from r1,1to r2,1. Note that the rule in G4,1,1and the rule in G5,1,1may start at different steps since the executions of rules G2,1and G3,1may finish at different steps. If the object t1(resp. f1) appears in membrane 3, under the influence of the protein r2,1on membrane 3, the application of rule G6,2,1(resp. G7,2,1) starts, the object t1(resp. f1) exits the membrane 3. With the object t1(resp. f1) in membrane 2 and the protein r2,1on membrane 3, the execution of one of rules in G4,2,1(resp. G5,2,1) starts, which corresponds to check whether the second clause is satisfied by the truth-assignment true (resp. false) of variable x1. The object t1(resp. f1) enters the membrane 3, and the object d2appears in membrane 2 if there exists object b2,1(resp. b 2,1) in membrane 3, otherwise, the object cappears in membrane 2. If the object t2(resp. f2) presents in membrane 3, under the influence of the protein r3,1on membrane 3, rule G6,3,1(resp. G7,3,1) is enabled and applied, the object t2(resp. f2) exits the membrane 3. In this way, rules in G4,i,1(1 ≤i ≤m) and rules G6,i,1(2 ≤i ≤m) (resp. rules in G5,i,1and rule G7,i,1) can be applied one by one. All the clauses are checked that whether they are satisfied by the truth-assignment true (resp. false) of variable x1. Rules G4,i,1and G5,i,1(2 ≤i ≤m) may start at different steps since the executions of rules G6,i,1and G7,i,1may complete at different steps, rules G6,i,1and G7,i,1(2 ≤i ≤m) may start at different steps since the executions of rules G4,i−1,1and G5,i−1,1may complete at different steps. If the protein rm+1,1is present on membrane 3, which contains the object t1(resp. f1), the application of rule G8,1 (resp. G9,1) starts, the object t1(resp. f1) evolves to a(1) 1(resp. a(2) 1), and the object a(1) 1(resp. a(2) 1) exits the membrane 3, changing the protein from rm+1,1to r1,2. With the object a(1) 1(resp. a(2) 1) in membrane 2 and the protein p+ 1(resp. p− 1) on membrane 2, rule G10,1(resp. G11,1) is enabled and used, the object a(1) 1(resp. a(2) 1) exits membrane 2 and the protein p+ 1 (resp. p− 1) placed on membrane 2 is changed to p− 1(resp. p+ 1). Note that rules G8,1and G9,1may start at different steps since the executions of rules G4,m,1and G5,m,1may complete at different steps, rules G10,1and G11,1may start at different steps due to the fact that the executions of rules G8,1and G9,1may complete at different steps. Rule G12,1is enabled only when the object a(2) 1appears in membrane 1 and there is a membrane 2 having the protein p− 1placed on it, that is, rule G12,1can be used only when the executions of both rules G10,1and G11,1have completed. Thus, rule G12,1plays a synchronization function because e(G2,1) +1≤i≤me(G4,i,1) +2≤i≤me(G6,i,1) +e(G8,1) +e(G10,1) may not equal to e(G3,1) +1≤i≤me(G5,i,1) +2≤i≤me(G7,i,1) +e(G9,1) +e(G11,1). Anyway, when the execution of rule G12,1 completes, the computation takes at most 4m +5 RS-steps, which is independent on any time-mapping e. By applying rule G12,1, the object a(2) 1evolves to a(3) 1and the object a(3) 1enters membrane 2. When the execution of rule G12,1finishes, under the influence of the protein p− 1placed on membrane 2, the application of rule G13,1starts, the object a(3) 1exits membrane 2 changing the protein from p− 1to p+ 1. With the object a(3) 1in membrane 1 and the protein q1on membrane 4, rule G14,1is enabled and applied, the object a(3) 1evolves to a2, and the object a2enters membrane 4, changing the protein from q1to q 1. When the protein q 1is present on membrane 4, rule G15,1is enabled and applied, membrane 4 is divided into two copies of membranes with the same label, and the protein q 1is replaced by q2on each membrane. The division rule G15,1has a copy function, which makes the number of the object a2doubled. When the protein q2appears on membrane 4, the application of rule G16,2in all membranes 4 starts and completes at the same step (the execution of rule G16,2in all membranes 4 takes the same time e(G15,1)for a given time-mapping e). By using rule G16,2, the object a2exits membrane 4. With the object a2in membrane 1 and the protein p+ 1on membrane 2, rule G17,1 is enabled and used, each object a2enters a membrane 2, changing the protein from p+ 1to p2(there are two copies of object a2in membrane 1 and two membranes 2 with protein p+ 1placed on, and the system works in a maximally parallel manner). In general, when the object a2appears in membrane 2, the computation takes at most 4m +10 RS-steps. The appearance of object a2in membrane 2 (or the protein p2appears on membrane 2) means that the system completes the following processes: assigning truth-assignment of variable x1, and looking for the clauses satisfied by the truth-assignment of variable x1; and the system starts the following processes: assigning truth-assignment of variable x2, and looking for the clauses satisfied by the truth-assignment of variable x2. When the protein p2appears on membrane 2, rule G1,2is enabled and applied. Note that the application of rule G1,2in all membranes 2 starts at the same step and completes at the same step, since the execution of rule G1,2in all membranes 2 takes the same time e(G1,2)for a given time-mapping e. The application of rules G2,2and G3,2starts at the same step, but may complete at different steps. Furthermore, the application of rules G4,i,2(1 ≤i ≤m), G5,i,2(1 ≤i ≤m), G6,i,2(2 ≤i ≤m), Fig. 1. The membrane structure at the moment when generation phase completes. G7,i,2(2 ≤i ≤m), G8,2, G9,2, G10,2and G11,2may start and complete at different steps. However, rule G12,2is enabled only when all rules that have started and completed their executions. Similar to the case of variable x1, the processes of assigning truth-assignment of variable x2as well as looking for the clauses satisfied by the truth-assignment of variable x2take at most 4m +10 RS-steps. The system continues to assign the truth-assignment of variables x3, x4, ..., xnand look for the clauses satisfied by the truth-assignment of variables. In general, after 4mn +10nRS-steps, 2ncopies of membrane with label 2 and 2ncopies of membrane with label 4 are generated, all of which are placed in membrane 1, and in each copy of membrane 2, there exists a membrane 3 (see Fig. 1 for the membrane structure at the moment when generation phase completes). Checking phase. When the generation phase completes, each membrane with label 2 contains some of objects from the set {d1, d2, ..., dm}, whose elements denote the corresponding clauses satisfied by the truth assignments of the variables. If there is at least one membrane with label 2 that contains all the objects d1, d2, ..., dm, which means the corresponding truth assignment in that membrane satisfies all clauses, hence formula ϕis satisfiable; if there is no membrane with label 2 that contains all the objects d1, d2, ..., dm, the formula ϕis not satisfiable. At the last of the generation phase, under the influence of the protein p+ non membrane 2, all the objects an+1enter membranes 2, changing the protein from p+ nto pn+1at the same step (there are 2ncopies of object an+1and 2ncopies of membrane 2, each object an+1enters a membrane 2 by applying the rule G17,nin a maximally parallel manner). Thus, the protein pn+1placed on each membrane with label 2 appears at the same step. When the execution of rule G17,ncompletes, the system starts to check whether the object d1presents in each membrane 2 (i.e., checking whether the corresponding true assignment satisfies the clause C1). If the object d1appears in a membrane 2, with the protein pn+1on membrane 2, rule C1,1is enabled and applied, the object d1exits membrane 2, changing the protein from pn+1to pn+2on membrane 2. When the execution of rule C1,1finishes, the system starts to check whether the object d2appears in a membrane 2 (i.e., checking whether the corresponding true assignment satisfies the clause C2). The proteins pn+3appear only when the corresponding membranes 2 contain the objects d2. The system continues to check whether the objects d3, d4, ..., dmappear in membranes 2. For any membrane 2 that does not contain the object di, i =1, 2, ..., m, then the computation in this membrane stops at the time when C1,iis supposed to be applied. In general, the checking phase takes at most mRS-steps (if there is a membrane 2 contains all objects d1, d2, ..., dm, the process takes mRS-steps). Output phase. In the initial configuration of the system, membrane 1 contains the object no. At step 1, with the protein son membrane 1, rule O4is applied, where the object no exits membrane 1, changing the protein from sto s. When checking phase finishes, we have the following two cases. •If no protein pn+m+1is present on any membrane with label 2, then rules O1, O2, O3cannot be applied. In this case, when the system halts, the object no remains in the environment, which means that the formula is not satisfiable. •If there exits at least one membrane 2 with the protein pn+m+1on it, then rule O1will be used, the object an+1evolves to yes, and the object yes exits membrane 2. When the execution of rule O1finishes, at this moment, if the execution of rule O4is not yet finished, then no rule can be started in the system. Only when the execution of rule O4completes, the protein on membrane 1 is changed to s, rule O2will be enabled. By applying rule O2, the object yes exits to the environment, changing the protein from sto s (it ensures that only one copy of object yes exits to the environment if there exists more than one copy of object yes in membrane 1). When the protein s presents on membrane 1, rule O3will be applied, the object no enters membrane 1. In this case, when the system halts, one copy of object yes remains in the environment, which means that the formula is satisfiable. This process takes three RS-steps. According to the analysis above, it is obvious that for any time-mapping e :R →N, the object yes appears in the environment when the computation halts if and only if the formula ϕis satisfiable; and the object no presents in the environment when the computation halts if and only if the formula ϕis not satisfiable. Thus, the system m,nis time-free sound and time-free complete. For any time-mapping e :R →N, if the formula ϕis satisfiable, the computation takes at most 4mn +10n +m +3 RS-steps: it takes at most 4mn +10nRS-steps to generate 2ncopies of membranes with label 2 and 2ncopies of membranes with label 4; it takes mRS-steps to check whether all clauses are satisfied by an assignment; the output phase takes three RS-steps, and the system halts. If the formula ϕis not satisfiable, the computation takes at most 4mn +10n +mRS-steps (it takes no RS-step at the output phase), and the system halts. Therefore, the family of P systems with proteins on membranes is time-free polynomially bounded. The family ={m,n|m, n ∈N}defined above is polynomially uniform by Turing machines because the construction of P system is built in a polynomial time with respect to the size parameters nand m, and necessary resources are as follows: –size of the set O: 3mn +6n +m +4; –size of the set P: mn +6n +m +6; – initial number of membranes: 4; –total size of initial multisets of objects: mn +2; – initial number of proteins on membranes: 4; –number of rules: 8mn +11n +m +4; –the maximal length of a rule including proteins: 6. We omit the detailed construction due to the fact that it is straightforward but cumbersome as explained in the proof of Theorem 7.2.3 in [16]. Therefore, the SAT problem can be solved in polynomial RS-steps by a family of recognizer P systems with proteins on membranes in a time-free uniform manner, and the length of evolution rules is at most 6. That is, we have shown that SAT ∈PMCtf CPE(6).2 4. Conclusions and further works In this work, we investigate the computational efficiency of timed P systems with proteins on membranes. Specifically, we construct a family of P systems with proteins on membranes, which solves SAT problem in a time-free uniform manner, where the correctness of the solution is irrelevant to the time used by the involved rules, and the P systems are constructed from the sizes of instances. The solution to SAT problem given in Section 3uses the division rules for elementary and non-elementary membranes. It remains open how we construct P systems with proteins on membranes and only elementary membrane division rules to time-freely solve the NP-complete problem. The P system constructed in the proof of Theorem 3.1 has the maximum length of evolution rules 6. It remains open whether the SAT problem can be efficiently solved by P systems with maximum length of evolution rules 4, that is, avoiding evolution rules of type (e). Flip-flop membrane systems with proteins are a particular class of P systems with proteins on membranes [12]. In such P systems, each protein has at most two states: pand ¯ p, and the rules are used either without changing the protein or changing the protein from pto ¯ pand back. It is of interest to investigate whether we can give a time-free uniform solution to SAT problem by using flip-flop membrane systems with proteins. Proteins that used to control evolution rules are also investigated in tissue-like P systems [22], where there is one and only one copy of protein placed on each cell, and multisets of objects together with proteins between cells are exchanged if a symport/antiport rule is used between these cells in a computation step. It remains open whether we can construct tissue-like P systems with protein on cells and cell division to solve NP-complete problems in the context of time-freeness. Recently, cell-like spiking neural P systems have been proposed in [28], where only one kind of objects (i.e., spikes) is considered. It is proved that cell-like spiking neural P systems as number generating devices are Turing universal [28]. It is interesting to construct cell-like spiking neural P systems with cell division to solve NP-complete problems. It is interesting to consider a more general variant of P systems with proteins on membranes where each application of a rule has an execution time and study if there exists clock-free uniform solution to SAT. Acknowledgments The work of B. Song and L. Pan was supported by National Natural Science Foundation of China (61033003, 61320106005 and 61472154), Ph.D. Programs Foundation of Ministry of Education of China (2012014213008), the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012). The work of M.J. Pérez-Jiménez was supported by “Ministerio de Economía y Competitividad” of Spain (TIN2012-37434), cofunded by FEDER funds.