# Time-Free Solution to SAT Problem by Tissue P Systems

Authors: Yueguo Luo; Zhongyang Xiong; Guanghua Zhang
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

Tissue P systems are a class of computing models inspired by intercellular communication, where the rules are used in the nondeterministic maximally parallel manner. As we know, the execution time of each rule is the same in the system. However, the execution time of biochemical reactions is hard to control from a biochemical point of view. In this work, we construct a uniform and efficient solution to theSAT problem with tissue P systems in a time-free way for the first time. With the P systems constructed from the sizes of instances, the execution time of the rules has no influence on the computation results. As a result, we prove that such system is shown to be highly effective for NP-complete problem even in a time-free manner with communication rules of length at most 3.


---

## Body

## 1. Introduction

As a well-known NP-complete problem,SAT problem has been widely used in artificial intelligence and electronic design automation. Many applications can be considered as a decision procedure to determine if a specific instance is SAT or UNSAT. As we know, some traditional SAT algorithms, such as DP [1] and Wu’s method [2], have an exponential time complexity. Compared with these algorithms, solving the SAT problem in a distributed and parallel manner may be an efficient method. Hence, we naturally consider the computing models in the framework of membrane computing, which can solve computationally hard problems efficiently.Membrane computing is a new area of computer science in recent years. It is introduced by Păun in [3]. Since then, this research area has been widely concerned by researchers. The computing models are inspired by biological phenomena and biological characteristics like other methods of natural computing, such as particle swarm optimization algorithms, ant colony algorithms, and genetic algorithms. The models abstract computing ideas from the structure and function of individual cells and from complexes of cells, such as tissues and organs (including the brain). Based on these biological facts, there are mainly three types of P systems which have been introduced: cell-like P systems, tissue P systems, and neural-like P systems. In traditional tissue P systems, rules are used in a synchronous, parallel, and nondeterministic way. Note that evolution rules in each cell follow the principle of maximal parallelism. Therefore, NP-hard problems can be solved efficiently. Until now, many kinds of P systems can solve some NP-complete problems, such as SAT [4–10], 3-coloring problem [11], and Hamiltonian cycle problem [12]. In addition, many new variants of P systems have equivalent computing power with Turing machine and to be Turing universal as language generators [13–15]. Inspired by some biological facts, several methods were proposed to produce new membranes in living cells: membrane division [5, 16], membrane creation [4], and membrane separation [7]. In this paper, we pay close attention to tissue P systems with cell division. In [16], tissue P systems with cell division were proposed. This computing model is inspired by the biological fact that cells are duplicated via mitosis. By this method, an exponential amount of cells can be generated. It has been proved that tissue P systems can solve some computational hard problems in polynomial time (even linear time). The first attempt in this topic was done in [16], where SAT problem was solved by tissue P systems with cell division in polynomial time.S A T problem has been widely investigated by cell-like P systems [4–8]. However, it is rarely investigated by tissue P systems. In [9, 16], SAT problem was solved by tissue P systems in polynomial time. However, in these works, each rule is assumed to be completed in one accurate unit time. Hence, every rule in these systems has the same execution time. However, the execution time of biochemical reactions is uncontrollable. Therefore, it is necessary to construct a system that works independently of the execution time of rules. The concept of time-free was first introduced in [17], and the open problems with solutions for NP-complete problems were formulated in [18]. Recently, some NP-complete problems have been solved in a time-free manner [19–23]. However, the model of these P systems is based on cell-like P systems. In this work, we solve SAT problem with timed tissue P systems by cell division in a uniform way. As far as we know, there are no other relevant papers on solving SAT problem with tissue P systems in a time-free manner.The paper is structured as follows: firstly, we give brief descriptions of the basic model of tissue P systems with cell division. Then, timed P systems with tissue P systems to decision problems will be proposed. In Section3, we prove that SAT problem can be solved by tissue P systems in a time-free way. Finally, some formal details and conclusions are presented.


## 2. Tissue P Systems with Cell Division

### 2.1. Tissue P Systems with Cell Division

The membrane structures of tissue P systems are described by general graphs, where cells correspond to nodes of a graph, and communication channels correspond to edges between two nodes. If there exists a communication channel, objects can communicate between two cells (or a cell and the environment) with communication rules.Definition 1.
Formally, a tissue P system (of degreem≥1) with cell division can be defined as the form(1)Π=O,E,w1,…,wm,R,iout,where(i)
O is the finite nonempty alphabet of objects,(ii)
E⊆O is the set of objects, which are initially placed in the environment with arbitrary number of copies,(iii)
wi(1≤i≤m) are finite multisets over O,(iv)
iout is output region of membrane structure, and it saves the results,(v)
R is a finite set of rules. There are mainly the following two forms:
(a)
communication rules:(i,u/v,j), where i,j∈{0,1,2,…,m}, i≠j,u,v∈O∗,uv>0, and i and j correspond to the cell i and cell j, respectively. When i=0 or j=0, it corresponds to the environment. If u≠λ and v≠λ, a communication rule is called an antiport rule; otherwise it is a symport rule. When there are objects represented by multiset u in cell i and objects represented by multiset v in cell j, a communication rule can be applied. With applying this rule, the objects denoted by u are sent into region j; at the same time, the objects denoted by v are sent into region i in the opposite direction. These objects can evolve by given rules in a synchronous, parallel, and nondeterministic way,(b)
division rules:ai→bici, where i∈{0,1,2,…,m}; a,b,c∈O;i≠iout. Under the influence of the object present in a cell, this rule can be applied to divide the cell into two copies of cells (with the same label with i); object b and object c in the two cells can be generated, respectively. The remaining objects in the original cell enter the newly generated cells, respectively. When a cell is being divided, the division rule is the only one which is applied for that cell at that step.Before the system begins to run, the initial configuration is represented by (w1,…,wm); that is, objects denoted by w1,…,wm are placed in the corresponding cells. We can get transitions between the configurations by applying rules of the system as described above. The current configuration is described by multisets of objects. Finally, the system will stop running. At that moment, there is no rule which is being applied, and no rule can be applied. In each cell, it must be stressed that the system works with the following principles:(i)
Nondeterminism: for each computation step, rules and objects are nondeterministically chosen; that is, any possible execution of rules can start randomly.(ii)
Maximal parallelism: at one computation step, if no other rules can be added to be applied, all rules which can be applied have to be applied to all possible objects.


### 2.2. Recognizer Timed Tissue P Systems with Cell Division

A P system that generates (or accepts) the same family of vectors of natural numbers, independently of the value assigned to the execution time of each ruler, is called time-free [18].Definition 2.
A recognizer timed tissue P system can be defined as the form(2)Π=O,Σ,E,w1,…,wm,R,e,iin,iout,where(i)
O is the finite nonempty alphabet of objects;(ii)
Σ is an (input) alphabet strictly contained in O, and Σ∩E=∅;(iii)
E⊆O is the set of objects, which are initially placed in the environment with arbitrary number of copies;(iv)
wi(1≤i≤m) are finite multisets over O;(v)
R is a finite set of rules;(vi)
we can specify the execution time of each rule by a mappinge: R→N, where N is the set of nonpositive integers;(vii)
iin∈{1,2,…,m} is the input cell;(viii)
iout is the environment, which saves the results;(ix)
the working alphabet contains two distinguished elementsyes and no;(x)
all the computations halt;(xi)
when the system halts, either objectyes or no (but not both) must appear in the environment.The input multiset has been added to the contents of the input celliin. Thus, we have an initial configuration associated with each input multiset. For the multiset w over the input alphabet Σ, the computation of the system with input w starts as the form(3)w1,…,wiin+w,…,wm.At one step, if no rules can be applied to the current configuration and no rules are being applying, the system will stop running. In this case, the object of output cell is computing result in the stopping configuration. If the objectyes appears in the environment when the system stops, it is anaccepting computation; on the contrary, if the object no appears, it is arejecting computation.Definition 3.
A timed tissue P system with cell division is a pair(Π,e), where Π is a tissue P system with cell division and e represent the execution times of the rules. We denote by Π(e) the timed tissue P system with cell division.Π ( e ) works in the following way: an external clock is supposed to mark time units of equal length, starting from time 0. If a rule r from R is selected to be executed, we denote e(r) as the time which the rule r lasts. If the application of a rule r starts at time j, the execution of this rule terminates at time j+e(r). It means that the rule lasts e(r) steps. The objects and the cells produced by the rule are not available until the beginning of step j+e(r)+1.


### 2.3. Polynomial Complexity Classes of Recognizer Timed Tissue P Systems with Cell Division

Definition 4.
LetX=(IX,θX) be a decision problem (with yes/no answer), where IX is a set of instances and θX is a predicate over IX, and let Π={Π(n)∣n∈N} be a family of recognizer P systems. We userule starting step (RS-step, for short) to define the computation step in timed P systems [18].Because the system works in a time-free manner, the execution time of each rule is no longer one accurate unit time.Π computes a solution of an instance, and the system works independently of any time mappinge. Hence, the systems Π can solve problemX in a time-free manner.Definition 5.
A decision problemX=(IX,θX) is solvable in polynomial time and in uniform way by a family Π={Π(n)∣n∈N} of recognizer timed tissue P systems, if the following holds:(1)
The familyΠ is polynomially uniform with respect to Turing machines; namely, there exists a deterministic Turing machine which constructs the system Π(n) with knowledge involving only the size of the problem X for every instance of X working in polynomial time.(2)
There exists a pair(cod,s) of polynomial time computable functions over IX such that
(i)
for each instanceu∈IX, s(u) is a natural number and cod(u) is an input multiset of the system Π(s(u)),(ii)
the familyΠ is time-free sound with regard to (X,cod,s). For each instance u∈IX such that there exists an accepting computation if Π(s(u),e) with input cod(u), we have θX(u)=1,(iii)
the familyΠ is time-free complete with regard to (X,cod,s). For each instance u∈IX, if θX(u)=1, then every computation of Π(s(u),e) with input cod(u) is an accepting one for any time mappinge,(iv)
the familyΠ is time-free polynomially bounded with regard to (X,cod,s); namely, there exists a polynomial function p(n) such that for each u∈IX, when all the computations in Π(s(u),e) with input cod(u) halt, there is at most p(u) RS-steps for any time mappinge.For the set of decision problems, we denote it withPMCTF-TP(k) which can be solved by recognizer timed tissue P systems and the length of evolution rules at most k working.


## 2.1. Tissue P Systems with Cell Division

The membrane structures of tissue P systems are described by general graphs, where cells correspond to nodes of a graph, and communication channels correspond to edges between two nodes. If there exists a communication channel, objects can communicate between two cells (or a cell and the environment) with communication rules.Definition 1.
Formally, a tissue P system (of degreem≥1) with cell division can be defined as the form(1)Π=O,E,w1,…,wm,R,iout,where(i)
O is the finite nonempty alphabet of objects,(ii)
E⊆O is the set of objects, which are initially placed in the environment with arbitrary number of copies,(iii)
wi(1≤i≤m) are finite multisets over O,(iv)
iout is output region of membrane structure, and it saves the results,(v)
R is a finite set of rules. There are mainly the following two forms:
(a)
communication rules:(i,u/v,j), where i,j∈{0,1,2,…,m}, i≠j,u,v∈O∗,uv>0, and i and j correspond to the cell i and cell j, respectively. When i=0 or j=0, it corresponds to the environment. If u≠λ and v≠λ, a communication rule is called an antiport rule; otherwise it is a symport rule. When there are objects represented by multiset u in cell i and objects represented by multiset v in cell j, a communication rule can be applied. With applying this rule, the objects denoted by u are sent into region j; at the same time, the objects denoted by v are sent into region i in the opposite direction. These objects can evolve by given rules in a synchronous, parallel, and nondeterministic way,(b)
division rules:ai→bici, where i∈{0,1,2,…,m}; a,b,c∈O;i≠iout. Under the influence of the object present in a cell, this rule can be applied to divide the cell into two copies of cells (with the same label with i); object b and object c in the two cells can be generated, respectively. The remaining objects in the original cell enter the newly generated cells, respectively. When a cell is being divided, the division rule is the only one which is applied for that cell at that step.Before the system begins to run, the initial configuration is represented by (w1,…,wm); that is, objects denoted by w1,…,wm are placed in the corresponding cells. We can get transitions between the configurations by applying rules of the system as described above. The current configuration is described by multisets of objects. Finally, the system will stop running. At that moment, there is no rule which is being applied, and no rule can be applied. In each cell, it must be stressed that the system works with the following principles:(i)
Nondeterminism: for each computation step, rules and objects are nondeterministically chosen; that is, any possible execution of rules can start randomly.(ii)
Maximal parallelism: at one computation step, if no other rules can be added to be applied, all rules which can be applied have to be applied to all possible objects.


## 2.2. Recognizer Timed Tissue P Systems with Cell Division

A P system that generates (or accepts) the same family of vectors of natural numbers, independently of the value assigned to the execution time of each ruler, is called time-free [18].Definition 2.
A recognizer timed tissue P system can be defined as the form(2)Π=O,Σ,E,w1,…,wm,R,e,iin,iout,where(i)
O is the finite nonempty alphabet of objects;(ii)
Σ is an (input) alphabet strictly contained in O, and Σ∩E=∅;(iii)
E⊆O is the set of objects, which are initially placed in the environment with arbitrary number of copies;(iv)
wi(1≤i≤m) are finite multisets over O;(v)
R is a finite set of rules;(vi)
we can specify the execution time of each rule by a mappinge: R→N, where N is the set of nonpositive integers;(vii)
iin∈{1,2,…,m} is the input cell;(viii)
iout is the environment, which saves the results;(ix)
the working alphabet contains two distinguished elementsyes and no;(x)
all the computations halt;(xi)
when the system halts, either objectyes or no (but not both) must appear in the environment.The input multiset has been added to the contents of the input celliin. Thus, we have an initial configuration associated with each input multiset. For the multiset w over the input alphabet Σ, the computation of the system with input w starts as the form(3)w1,…,wiin+w,…,wm.At one step, if no rules can be applied to the current configuration and no rules are being applying, the system will stop running. In this case, the object of output cell is computing result in the stopping configuration. If the objectyes appears in the environment when the system stops, it is anaccepting computation; on the contrary, if the object no appears, it is arejecting computation.Definition 3.
A timed tissue P system with cell division is a pair(Π,e), where Π is a tissue P system with cell division and e represent the execution times of the rules. We denote by Π(e) the timed tissue P system with cell division.Π ( e ) works in the following way: an external clock is supposed to mark time units of equal length, starting from time 0. If a rule r from R is selected to be executed, we denote e(r) as the time which the rule r lasts. If the application of a rule r starts at time j, the execution of this rule terminates at time j+e(r). It means that the rule lasts e(r) steps. The objects and the cells produced by the rule are not available until the beginning of step j+e(r)+1.


## 2.3. Polynomial Complexity Classes of Recognizer Timed Tissue P Systems with Cell Division

Definition 4.
LetX=(IX,θX) be a decision problem (with yes/no answer), where IX is a set of instances and θX is a predicate over IX, and let Π={Π(n)∣n∈N} be a family of recognizer P systems. We userule starting step (RS-step, for short) to define the computation step in timed P systems [18].Because the system works in a time-free manner, the execution time of each rule is no longer one accurate unit time.Π computes a solution of an instance, and the system works independently of any time mappinge. Hence, the systems Π can solve problemX in a time-free manner.Definition 5.
A decision problemX=(IX,θX) is solvable in polynomial time and in uniform way by a family Π={Π(n)∣n∈N} of recognizer timed tissue P systems, if the following holds:(1)
The familyΠ is polynomially uniform with respect to Turing machines; namely, there exists a deterministic Turing machine which constructs the system Π(n) with knowledge involving only the size of the problem X for every instance of X working in polynomial time.(2)
There exists a pair(cod,s) of polynomial time computable functions over IX such that
(i)
for each instanceu∈IX, s(u) is a natural number and cod(u) is an input multiset of the system Π(s(u)),(ii)
the familyΠ is time-free sound with regard to (X,cod,s). For each instance u∈IX such that there exists an accepting computation if Π(s(u),e) with input cod(u), we have θX(u)=1,(iii)
the familyΠ is time-free complete with regard to (X,cod,s). For each instance u∈IX, if θX(u)=1, then every computation of Π(s(u),e) with input cod(u) is an accepting one for any time mappinge,(iv)
the familyΠ is time-free polynomially bounded with regard to (X,cod,s); namely, there exists a polynomial function p(n) such that for each u∈IX, when all the computations in Π(s(u),e) with input cod(u) halt, there is at most p(u) RS-steps for any time mappinge.For the set of decision problems, we denote it withPMCTF-TP(k) which can be solved by recognizer timed tissue P systems and the length of evolution rules at most k working.


## 3. A Time-Free Uniform Solution toSAT Problem Using Tissue P Systems

Definition 6.
TheSAT problem is, for a Boolean formula of CNF, to look for whether or not there exists an assignment to its variables on which it is evaluated to be true [4].TheSAT problem is a well-known NP-complete problem. This problem has been widely used in artificial intelligence and computer theories. Boolean formula containingn variables has 2n values. By membrane division, we can obtain 2n membranes inn steps. In addition, by the maximal parallelism, we can obtain polynomial (maybe, linear) solutions to NP-hard problems. In what follows, we will propose a time-free uniform solution to the SAT problem; that is, P systems are constructed from the size of instances of the SAT problem in a time-free manner.Theorem 7.
S A T problem can be solved by a uniform family of timed tissue P systems by cell division.Proof.
For aSAT formula with n Boolean variables and m clauses, its CNF form is input into P systems. Let us consider a propositional formula γ=C1∧C2∧⋯∧Cm, consisting of m clauses Cj=y1,j∧⋯∧ypj,j, where yi,j∈{xl,¬xl∣1≤l≤n}. 1≤i≤pj, 1≤j≤m.
Let us consider the polynomial–time computable function (the pair function)(4)gn,k=n+kn+k+12+n.It is a primitive recursive and bijective function from ℕ2 to ℕ.The instanceγ is encoded by multiset as follows:(5)codγ=α1,1α1,2⋯α1,mα2,1α2,2⋯α2,m⋯αn,1αn,2⋯αn,m.We codifyγ, where for 1≤i≤n, 1≤j≤m, by the multiset (6)αi,j=βi,jifxiappearsinCj,βi,j¯if¬xiappearsinCj,βi,j0ifxiand¬xido  not  appear  inCj.Next, we define a family of recognizer tissue P systems with cell division, which can process all instances γ provided the appropriate input multiset cod(γ). The instance γ will be processed by the tissue P system with input cod(γ). For the given n variables and m clauses, we construct the recognizer tissue P system as follows:(7)ΠSATm,n=O,Σ,E,w1,w2,R,e,iin,iout,where(i)
O is the finite alphabet of the system,O=Σ∪ai1≤i≤n+1∪ti,j,fi,j1≤i≤n,1≤j≤m+1∪ei2≤i≤n+1∪bi,j,Ti,Fi,rj1≤i≤n,1≤j≤m∪sj2≤j≤m+1∪d,yes,no,the objects in theO mainly contain
(a)
ti,j denotestrue of the Boolean value for the variable;(b)
fi,j denotesfalse of the Boolean value for the variable;(c)
the objectyes means that the CNF is satisfiable;(d)
the objectno means that the CNF is unsatisfiable,(ii)
Σ={βi,j,βi,j0,β¯i,j∣1≤i≤n,1≤j≤m} is the input alphabet contained inO,(iii)
E is the arbitrary copies of objects in the environment,E=ai2≤i≤n+1∪ti,j,fi,j1≤i≤n,2≤j≤m+1∪ei2≤i≤n+1∪bi,j,Ti,Fi,rj1≤i≤n,1≤j≤m∪sj2≤j≤m+1∪d,(iv)
wi (1≤i≤m) are finite multisets over O,w1={yes,no}, w2=a1,(v)
iin = 2 is the input cell; iout=0 is the output region which saves the results,(vi)
We can specify the execution time of each rule by a mappinge: R→N, where R is the set of rules of ΠSAT(m,n). R is the following set of rules.(a) Generation Phase (8) R 1 , i : a i 2 ⟶ t i , 1 2 f i , 1 2 ,  1 ≤ i ≤ n , R t R 2 , i , j : 2 , t i , j β i , j / b i , j , 0 , 2 , b i , j / r j t i , j + 1 , 0 ,   1 ≤ i ≤ n ,   1 ≤ j ≤ m , R 3 , i , j : 2 , t i , j β i , j ¯ / t i , j + 1 , 0 ,  1 ≤ i ≤ n ,   1 ≤ j ≤ m , R 4 , i , j : 2 , t i , j β i , j 0 / t i , j + 1 , 0 ,  1 ≤ i ≤ n ,   1 ≤ j ≤ m , R f R 5 , i , j : 2 , f i , j β i , j ¯ / b i , j , 0 , 2 , b i , j / r j f i , j + 1 , 0 ,   1 ≤ i ≤ n ,   1 ≤ j ≤ m , R 6 , i , j : 2 , f i , j β i , j / f i , j + 1 , 0 ,  1 ≤ i ≤ n ,   1 ≤ j ≤ m , R 7 , i , j : 2 , f i , j β i , j 0 / f i , j + 1 , 0 ,  1 ≤ i ≤ n ,   1 ≤ j ≤ m , R 8 , i : 2 , t i , m + 1 / T i d , 0 ,  1 ≤ i ≤ n , R 9 , i : 2 , f i , m + 1 / F i d , 0 ,  1 ≤ i ≤ n , R 10 , i : 2 , T i / λ , 1 ,  1 ≤ i ≤ n , R 11 , i : 2 , F i / λ , 1 ,  1 ≤ i ≤ n , R 12 , i : 1 , T i F i / e i + 1 , 0 ,  1 ≤ i ≤ n , R 13 , i : 1 , e i / a i 2 , 0 ,  2 ≤ i ≤ n + 1 , R 14 , i : 2 , d / a i , 1 ,  2 ≤ i ≤ n + 1 .(b) Checking Phase (9) R 15 : 2 , a n + 1 r 1 / s 2 , 0 , R 16 , j : 2 , s j r j / s j + 1 , 0 ,  2 ≤ j ≤ m .(c) Output Phase (10) R 17 : 1 , n o / λ , 0 , R 18 : 2 , s m + 1 / y e s , 1 , R 19 : 2 , y e s / n o , 0 .The computing process consists of the following phases:(a)
Generation phase: all assignments of variables can be generated by using membrane division. Finally,2n copies of membranes can be generated.(b)
Checking phase: the system checks whether or not the formula has a truth assignment. If all assignments of variables cannot satisfy the clause, it means that there is no satisfiable solution; or it means that there is at least one satisfiable solution.(c)
Output phase: the objectyes/no of output membrane is computing result in the stopping configuration.The multiset of an instance is introduced into input cell of the system, and we can get the initial configuration. In what follows, we will give an overview of computing process to show how the system works. In order to have a global understanding of the subsequent process of proof, we classify all the rules as follows:(i)
R1,i(1≤i≤n) are division rules which can be used to produce an exponential space.(ii)
The rulesRt and Rf are used to check whether the corresponding clauses are satisfied by the assignmenttrue orfalse of variable xi (1≤i≤n).(iii)
The rules fromR8,i,j to R14,i are used for the next iteration of variable xi or preparing for checking phase.(iv)
With the rulesR15 and R16,i, the final detection results can be generated in each cell.(v)
With the rules fromR17 toR19, the system sends to the environment the final answer.(a) Generation Phase. Let e be the execution time of the rules. Initially, cell 1 contains objects yes and no; cell 2 contains objecta1, cod(γ). Objecta1 in cell 2 corresponds to variable x1.In general, objectsai in the cell with label 2 correspond to variable xi, 1≤i≤n. Boolean formula containing n variables has 2n values. By cell division, 2n copies of cells can be generated in n steps. Hence, we can obtain all the possible solutions of SAT problem in the end. At step 1, the system starts running, and rulesR1,1 andR17 can be applied at the same time. RuleR1,1 is a division rule, which can be applied to divide this cell into new cells with the same label. At the same time, objecta1 evolves to objectst1,1 and f1,1 in the two newly generated cells: objectt1,1 corresponds to assignmenttrue of variable x1, and object f1,1 corresponds to assignmentfalse of variable x1. In this process, there is only one RS-step because no other rules can be applied except for the rulesR1,1 andR17. When the execution of ruleR1,1 finishes, a rule in Rt (resp., Rf) can be enabled. These rules correspond to check whether the assignment (true orfalse) to the variable x1 in each clause is satisfiable.When objectt1,j and object β1,j appear in cell 2 or object f1,j and object β1,j¯ appear in cell 2, it means that the assignment of the current variable x1 can satisfy the clause. At this moment, by the application of the first rule in R2,i,j (resp., R5,i,j), object bi,j can be generated. When the execution of this rule has completed, the second rule in R2,i,j (resp., R5,i,j) can be applied. By using the rule, object bi,j in cell 2 can be sent out the cell, and object rj can be generated, which represent that this clause can be satisfied by the assignment. For object t1,j (resp., f1,j), 1≤i≤n, by using the rule R2,i,j, R3,i,j, or R4,i,j (resp., R5,i,j, R6,i,j, or R7,i,j), the second component of the subscript will increase one by one. In general, for the current variable xi (1≤i≤n), there are m clauses; that is, the second component of the subscript can reach to m+1 in the end. Thus, when the application of all the rules in Rt (resp., Rf) completes, object ti,m+1 (resp., fi,m+1) can be generated. Because the first two rules in Rt and Rf are started at the same time, these two rules take only one RS-step. In addition, we consider maximum number of rules in Rt and Rf, namely, R2,i,j and R5,i,j. Note that the two rules (R2,i,j and R5,i,j) cannot be executed together because the same variable in the same clause is either xi or ¬xi. Therefore, it takes at most 3m-1 RS-steps to complete this process.Figure1 shows the division process of n variables, which can be represented by a binary tree. Each variable of a CNF formula is divided into two parts in an iterative manner. Each node of the binary tree is assigned totrue orfalse, which represents the assignment of a variable. Left and right subtree branches indicate thetrue value and thefalse value, respectively. For every iteration of variable xi, when the execution of rule Rt (resp., Rf) finishes, at that moment, object ti,m+1 (resp., fi,m+1) can be generated in every cell with label 2. For example, for the iteration of variable x3 in Figure 1, there are four copies of object ti,m+1 (resp., fi,m+1) generated at the same time. When division rule completes, the rules in Rt and Rf start simultaneously in each cell 2. For every cell containing object ti,m+1 (resp., fi,m+1), in which the same rules are applied, object ti,m+1 (resp., fi,m+1) in each cell with label 2 is generated at the same time. But ti,m+1 and fi,m+1 cannot be generated at the same time because the execution time of rules in Rt and Rf is different.Figure 1
The division process of variables.According to the analysis above, the applications of rulesR8,1 and R9,1 start at different steps. When an object t1,m+1 (resp., f1,m+1) is generated, rule R8,1 (resp., R9,1) can be applied, by which cell 2 sends out object t1,m+1 (resp., f1,m+1) to the environment and receives multiset T1d (resp., F1d) from the environment. Thus, the application of rule R8,i (resp., R9,i) can ensure that only one copy of objectd can be generated in each cell with label 2. When the object T1 (resp., F1) is generated in a cell 2, ruleR10,1 (resp., R11,1) is applied, by which object T1 (resp., F1) can be sent to cell 1. When the execution of both rule R10,1 and rule R11,1 finishes, rule R12,1 can be applied. At this moment, object T1 and F1 can appear in the cell 1. By using the rule R12,1, object T1 and F1 in cell 1 can be sent out that cell. At the same time, object e2 enters the cell 1.As we know, it is obvious thate(Rt) + e(R8,1) + e(R10,1) may not be equal to e(Rf)+e(R9,1)+e(R11,1) because the system works independently of the execution time of rules. Hence, the rule R12,1 is applied to solve synchronization problem of the rules. When the application of rule R12,1 finishes, the execution of all the aforementioned rules has completed. At that moment, cell 1 has one copy of object e2. By using the rule R13,2, two copies of objecta2 enter the cell 1. Note that each cell 2 has an objectd; by using the rule R14,2, each cell 2 will obtain one copy of object a2 simultaneously because of the principle of maximal parallelism; that is, all of the rules that can be applied must be applied simultaneously. Note that only one copy of object d appears in each cell with label 2; eventually, each cell 2 contains one copy of object ai+1.The system runs in this way, and objecta2 must appear in each cell 2 simultaneously. When the application of rule R14,2 is completed, note that the execution of all the aforementioned rules has been completed for the first iteration of variable xi (1≤i≤n). These available rules are applied in the order{R1,1}→{{R2,1,j,R3,1,j,R4,1,j}→{R8,1}→{R10,1}(resp.,{R5,1,j,R6,1,j,R7,1,j}→{R9,1}→{R11,1})}→{R12,1}→{R13,2}→{R14,2}.When the application of all rules above is completed, it takes at most3m+7 RS-steps.When the first iteration of variablexi (1≤i≤n) is completed, every cell 2 contains object a2. Under the influence of object a2, rule R1,2 can be applied simultaneously. With the application of the division rule, four cells with label 2 can be generated. Similarly, the system executes the above process in an iterative manner till the assignments of all the variables are obtained.The available rules fromR1,1 to R14,n are applied in the following order:The application of rules for the first iteration:{R1,1}→{{R2,1,j,R3,1,j,R4,1,j}→{R8,1}→{R10,1}(resp.,{R5,1,j,R6,1,j,R7,1,j}→{R9,1}→{R11,1})}→{R12,1}→{R13,2}→{R14,2}.The application of rules for the second iteration:{R1,2}→{{R2,2,j,R3,2,j,R4,2,j}→{R8,2}→{R10,2}(resp.,{R5,2,j,R6,2,j,R7,2,j}→{R9,2}→{R11,2})}→{R12,2}→{R13,3}→{R14,3}.⋮The application of rules for the last iteration:{R1,n}→{{R2,n,j,R3,n,j,R4,n,j}→{R8,n}→{R10,n}(resp.,{R5,n,j,R6,n,j,R7,n,j}→{R9,n}→{R11,n})}→{R12,n}→{R13,n+1}→{R14,n+1}.In general, when the application of rules fromR1,1 to R14,n is completed, this computation process takes at most 3mn + 7n RS-steps.When objectan+1 occurs in an arbitrary cell 2, it means that the execution of all the aforementioned rules has been completed. Note that the application of R13,n+1 and R14,n+1 in each cell follows the principle of maximal parallelism. Therefore, objects an+1 in each cell 2 can be generated simultaneously.(b) Checking Phase. When the execution of rule R14,n+1 is completed, there are some objects (or no object) from the set {r1,r2,…,rn} in every cell 2. These objects represent that the corresponding clauses can be satisfied. Thus, if at least one cell contains all objects including r1,r2,…,rn, it means that there is a satisfiable solution; or it means that there is no satisfiable solution. At this moment, rule R15 is applied in each cell 2 simultaneously. With the appearance of object an+1 and object r1 (if this object exists in a cell 2) in cells 2, by using the rule R15, the object r1 is checked and s2 can be sent to cell 2 from the environment. If the object si (2≤i≤m) appears in a cell 2, rule R16,i can be applied. Eventually, if the object sm appears in a cell 2, rule R16,m can be applied. Thus, object sm+1 can be generated in that cell. Please note that the rules are used in a time-free manner. In addition, although there may be more than one copy of object ri (1≤i≤m), only one copy can be applied by the rules of R15 and R16,i. In general, this computation process takes at most m RS-steps.(c) Output Phase. When the checking phase and the execution of ruleR17 are complete, there are the following two cases:(i)
Affirmative answer: in this case, object sm+1 is generated in a cell 2, telling us that the formula is satisfiable; by using the ruleR18, objects sm+1 can be sent out to cell 1; at the same time, object yes enters the cell 2. Eventually, by using the ruleR19, the object yes in one cell 2 can be sent out to the environment; at the same time, object no enters the cell 2. Thus, if the system halts, object yes is in the environment; we can draw a conclusion that there is at least one satisfiable solution. Hence, in this case, the formula is satisfiable. This process takes 2 RS-steps.(ii)
Negative answer: in this case, object sm+1 does not appear in a cell with label 2. Therefore, the ruleR18 and ruleR19 cannot be applied. Eventually, when the system halts, if object no is still in the environment, we can draw a conclusion that there is no satisfiable solution. Hence, in this case, the formula is not satisfiable. This process takes no RS-step.


## 4. Some Formal Details

For aSAT instance with n Boolean variables and m clauses, the necessary resources to construct ΠSAT(m,n) can be drawn as follows:(i)
Size of the setO: 6mn + 6n + 2m + 4.(ii)
Initial number of cells: 2.(iii)
Initial number of objects: 3.(iv)
The total number of rules: 8mn + 8n +m + 3.(v)
The maximal length of a rule: 3.Π S A T ( m , n ) always halts till the output is yes or no in the end. As a recognizer tissue P system, the system stops working within a certain RS-steps. Hence, eventually, object yes or no must appear in the environment in a feasible time. According to the analysis in Section 3, if the formula γ is satisfiable, then after at most 3mn + 7n +m + 2 RS-steps the P systems will stop working; if the formula γ is not satisfiable, then after at most 3mn + 7n +m RS-steps the P systems will stop working. For both cases, the generation phase takes at most 3mn + 7n RS-steps, and the checking phase takes at mostm RS-steps; for output phase, the former takes at most 2 RS-steps, and the latter takes no RS-step.Obviously, there is a polynomial bound of the computation for the system. TheSAT problem can be solved in polynomial RS-steps by a family of recognizer timed tissue P systems. Hence, the constructed P systems have high computational efficiency to solve the NP-hard problems even in the time-free manner.Theorem 8.
A family of a timed tissue P system can be constructed as a uniform solution to theSAT problem in a time-free way. For any time mappinge, the execution time of the rules does not influence the results of the system.Proof.
Π S A T ( m , n ) always halts till the output is yes or no in the end. According to the analysis above, the SAT can be solved by a family of recognizer tissue P systems in polynomial RS-steps. Hence, the ΠSAT(m,n) have the powerful computational efficiency to solve the computationally hard problem. Furthermore, the execution time of rules has no influence on the computation results.
It is easy to prove thatΠSAT(m,n) is time-free sound, time-free complete, and time-free polynomially bounded. Hence, we can draw a conclusion that it is a time-free solution to the SAT problem.Theorem 9.
S A T ∈ P M C T F - T P ( 3 ).Proof.
It suffices to remark that theSAT problem is NP-complete. Note that the family of recognizer P systems given in Section 3 has the length of communication rules which is no more than 3. According to Definition 5 and from the discussion in the previous subsections, it is easy to prove PMCTF-TP(3) and that this complexity class is closed under polynomial time reduction and under complement.Corollary 10.
N P ∪ c o - N P ⊆ P M C P F ( 3 ).


## 5. Conclusions

In this work, time-free method is introduced into tissue P systems. We consider that the lasting time of the chemical communication between living cells is often different, because it is influenced by many factors. Thus, a time mapping is added to specify the execution time of rules. Compared with traditional tissue P systems, it is a more realistic model from a biological point of view. The output of the timed tissue P system has no influence on the correctness of the solutions. We prove thatSAT problem can be efficiently solved by a family of timed tissue P systems with cell division and communication rules with length at most 3, which is a relatively good result from the computational complexity point of view in the time-free way. Our work provides a new and effective solution to SAT problem in a distributed and parallel manner.Finally, the reader can consider further problems. For instance, in Section3, we prove that NP-complete problem can be solved by timed tissue P systems with communication rules with length at most 3. We can consider what will happen if only symport rules or antiport rules are allowed in timed tissue P systems.



---

*Source: 1567378-2017-02-23.xml*