# Time-Free Solution to Hamilton Path Problems Using P Systems withd-Division

Authors: Tao Song; Xun Wang; Hongjiang Zheng
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

P systems withd-division are a particular class of distributed and parallel computing models investigated in membrane computing, which are inspired from the budding behavior of Baker’s yeast (a cell can generate several cells in one reproducing cycle). In previous works, such systems can theoretically generate exponential working space in linear time and thus provide a way to solve computational hard problems in polynomial time by a space-time tradeoff, where the precise execution time of each evolution rule, one time unit, plays a crucial role. However, the restriction that each rule has a precise same execution time does not coincide with the biological fact, since the execution time of biochemical reactions can vary because of external uncontrollable conditions. In this work, we consider timed P systems with d-division by adding a time mapping to the rules to specify the execution time for each rule, as well as the efficiency of the systems. As a result, a time-free solution to Hamiltonian path problem (HPP) is obtained by a family of such systems (constructed in a uniform way), that is, the execution time of the rules (specified by different time mappings) has no influence on the correctness of the solution.


---

## Body

## 1. Introduction

Membrane computing, introduced in [1], is one of the recent branches of natural computing. The computing systems investigated in membrane computing are distributed and parallel computing devices, usually called P systems. The aim is to abstract computing concepts and ideas (i.e., models, data structures, data manipulation operations, operation control modes, etc.) from the structure and the functioning of living cells, considered both individually and as part of complexes, such as tissues and organs like the brain. There are two main classes of P systems investigated: cell-like P systems [1] and tissue-like P systems [2]. In the cell-like P systems, the membrane structure graphically represented by a tree and in tissue-like P systems, the membrane structure is a general graph. In tissue-like P systems, we can find tissue P systems, neural P systems, and numerical P systems. Such three models have different alphabets, rules, and semantics, but all three keep the same membrane structure [3]. During the past years, many variants of P systems have been developed and proved to be universal (do what Turing machine can do) [4–6], and a particular class of P systems with cell reproduction properties (such as P systems with active membranes [7], tissue P systems with cell division [8], and spiking neural P systems with budding [5]) that can theoretically generate exponential working space in linear time have been used to solve computational hard problems in polynomial (even in linear) time [8–10]. An introduction to the area of membrane computing can be found in [7], while an overview of this field can be found in [3, 11], with up-to-date information available at the membrane computing website [12]. In the present work, we deal with a variant of cell-like P systems with active membranes, called P systems with d-division, which was inspired from the budding behavior of Baker’s yeast (a cell can generate several new cells in a reproducing cycle) [7].Briefly, a P system withd-division consists of a hierarchical membrane structure, a number of objects and evolution rules. In every membrane, objects (represented by multisets over a given alphabet) and evolution rules are present, where objects correspond to the chemical compounds that exist inside the cells, and the evolution rules correspond to the chemical reactions taking place in the cells. By using the evolution rules, objects can evolve to other objects, and the membrane structure can change. The membranes can also have an electrical charge, positive (+), negative (−), or neutral (0). A global clock is assumed to mark the time for the system. In each instant, if a rule is applicable over objects existing inside a membrane, the rule must be applied on the tick of the clock. If more than one rule is applicable at certain moment, one of these rules is nondeterministically chosen to use. Each cell in the systems works in a sequential way; in each time unit only one evolution can be used, but; for different cells, they work in a synchronous way. The configuration of the systems at a given instant of time is described by both the membrane structure and the multisets of objects present in each membrane. The systems can proceed from one configuration to another by applying evolution rules (it is said that a transition takes place from one configuration to the next one), which takes exactly one time unit. A sequence of transitions between configurations define a computation. A computation halts if it reaches a configuration where no rule can be applied in any membrane. In this case, the result of the computation can be interpreted as the number of objects inside a specified output membrane. P systems with d-division (d≥2) can theoretically generate exponential working space in linear time and thus provide a way to solve computational hard problems in polynomial time by a time-space tradeoff, where the precise execution time of each evolution rule (one time unit) plays a crucial role [7].In [8], inspired by the mitosis function of living cells, tissue P systems with cell division were proposed. The system can generate working space (cells) by using cell division rules and thus can generate exponential working space in linear steps. The newly generated working space provides a rich source for computation, particular for solving computational hard problems. In [8], tissue P systems with cell division can solve SAT problem in a polynomial time.In [7, 12], many variants of P systems with different strategies of generating working space have been reported, such as P systems with cell separation and SN P systems with budding. These systems can expand working space (by generating new cells or neurons) during the computation and thus can be used to solve computation hard problems in feasible (polynomial or even linear) time.In the results, the time cost of a computation is obtained by counting the steps used in the computation to solve the problem. In the systems, a global clock is assumed to mark the time of the systems, and there is a restriction that each biological operation should be completed in exactly one time unit, even for different operations. In P systems, each operation usually corresponds to a particular biochemical reaction, so it is not natural to impose that different operation should cost the same time.However, programming living things cannot assume neither general restrictions on execution time nor the presence of global clocks synchronizing the execution of different parallel processes. Moreover, the time of execution of certain biological processes could vary because of external uncontrollable conditions. Therefore, it seems crucial to investigate P systems when such timing assumption is not used.In this work, we consider P systems withd-division without the time assumption, which is achieved by adding a time mapping to specify the execution time of all the rules in the systems. The obtained systems are close to the biological fact, and their computational properties, particularly in computational efficiency, need to be investigated. The systems with d-division are considered by adding a time mapping to the rules to specify the execution time of each rule. The obtained systems are called timed tissue P systems with d-division. Particularly interesting are time-free P systems with d-division where, given an arbitrary time mapping for a system, results computed by the system are always the same, independent of the assigned time mapping. Following this line of work, finding solutions for hard computational problems by means of time-free systems was explored in [13] from a theoretical point of view. In this paper, we prove (in a constructive way) that we can solve NP-complete problems by means of time-free P systems with d-division. Specifically, a family of time-free P systems with d-division, constructed in a uniform way, capable of solving HPP problem are presented.


## 2. Preliminaries

In what follows some required concepts of formal language theory are presented as the necessary background for the topics covered in subsequent sections of this paper. Readers needing additional background can refer to works such as [14].For an alphabetV, V* denotes the set of all finite strings of symbols from V, while the empty string is denoted by λ, and the set of all nonempty strings over V is denoted by V+.Byℕ we denote the set of nonpositive integers. Let U be arbitrary set. A multiset (over U) is a mapping M:U→ℕ. The multiplicity of a in the multiset M can be denoted by M(a) with any a∈U. It can be expressed by the pair (a,M(a)). If the set U={a1,a2,…,an} is finite, a multiset M over U, represented by the set of mappings {(a1,M(a1)),(a2,M(a2)),…,(an,M(an))} can also be represented by a string w=a1M(a1)a2M(a2)⋯anM(an) or by any of its permutations.In what concern to the rest of this paper, we will not distinguish between the representation of multiset in mapping form or string form.


## 3. Time-Free Solutions to Decision Problems by Means of P Systems withd-Division

It is started by briefly recalling the formal definition of P systems withd-division introduced in [7], and then a timed extension of such systems is reviewed, followed by a description of time-free P systems with d-division. Finally, some notions of time-free solutions to decision problems by means of such systems are discussed.


### 3.1. P Systems withd-Division

AP system withd-division (d≥2) of degree m is a construct
(1)Π=(O,H,μ,w1,…,wm,R),where(i)
m≥1 is the initial number of membranes of the system;(ii)
O is the alphabet of objects;(iii)
H is a finite set of labels for membranes;(iv)
μ is the initial membrane structure, consisting of m membranes; membranes are labelled (not necessarily in an injective way) with elements of H and are electrically polarized, being possible charge positive (+), negative (−), or neutral (0);(v)
w1,…,wm are strings over O, describing the initial multisets of objects placed in the m regions of μ;(vi)
R is a finite set of evolution rules, of the following types:
(a)
[a→v]hα, h∈H,α∈{+,-,0},a∈O,v∈O*;(b)
a[]hα1→[b]hα2, h∈H,α1,α2∈{+,-,0},a,b∈O;(c)
[a]hα1→[]hα2b, h∈H,α1,α2∈{+,-,0},a,b∈O;(d)
[a]hα→b, h∈H,α∈{+,-,0},a,b∈O;(e)
[a]hα→[b1]hα1[b2]hα2⋯[bd]hαd,h∈H,α1,α2,…,αd∈{+,-,0},a,b1,b2,…,bd∈O;(f)
[[]h1α1⋯[]hkα1[]hk+1α2⋯[]hnα2]h0α0→[[]h1α3⋯[]hkα3]h0α5[[]hk+1α4⋯[]hnα4]h0α6, k≥1,n>k,hi∈H,0≤i≤n, and α0,…,α6∈{+,-,0} with {α1,α2}={+,-}.Rules of type (a) are objects evolution rules, whose application is controlled by both the label and the charge of the membranes. Rules of type (b) and (c) are communication rules, by which an object can be sent into or out of the membrane. The objects can be possibly modified during this process, as well as the polarization of the membrane can be changed, but not its label. The dissolving rules are of type (d), by which a membrane can be dissolved, while the object specified in the rule can be modified. The division rules for elementary membranes are of type (e). In reaction with an object, the elementary membrane can be divided intod membranes with the same labels, possibly of different polarizations; the object specified in the rule is replaced by some newly generated objects in the newly membranes. As shown in rules of type (f), if a membrane contains other membranes that have charges + or − but have globally neutral charge, these membranes with same charges can be be separated into two new membranes. The previous rules can be considered as “standard” rules; two possible extensions for rules of type (e) can be also considered:(e′)
[a]hα→[b1]h1α1[b2]h2α2⋯[bd]hdαd, h,h1,h2,…hd∈H,α,α1,α2,…,αd∈{+,-,0},a,b1,b2,…,bd∈O,d≥2;(e′′)
[a]hα1→[b1]hα2[b2]hα2⋯[bd]hαd, h∈H,α1,α2,…,αd∈{+,-,0},a,b1,b2,…,bd∈O, d≥2.By rules of type (e′), the membranes produced by division possibly have different labels with the divided membrane, and the polarizations of the new membranes can be different from the polarization of the initial one. Division rules (e′′) allow the division of nonelementary membranes, where all membranes from the initial membranes will be replicated and will appear in the new copies of this membrane.In each time unit (a global clock is assumed, marking the time for the whole system), the selected rules to be executed in each cell are applied on the tick of the clock, taking exactly one time unit to complete their execution. In a given time, if an object can evolve by more than one rules, only one of the rules is nondeterministically selected. All objects and membranes not specified in any executed rule remain unchanged.If a membrane is dissolved, all the objects contained in the region delimited by such membrane are left free in the surrounding region. If in a given computation step a membrane is divided and there are objects in this membrane which can evolve, it is assumed that evolution of objects takes place first; thus, the evolved objects will be present in the divided membranes. Objects that do not evolve are replicated. Thus, rules are applied “bottom-up”; that is, rules in the innermost membrane are applied first and, subsequently, level by level up to the region of the skin membrane. The skin membrane can never divide, but it can be “electrically charged.”Note that every cell in the systems works in a sequential way, in each time unit only one evolution can be used, but, for different cells, they work in a synchronous way.The configuration of the system at a given time unit is described by both the membrane structure and the multisets of objects present in each cell. By applying the rules specified above, one can define a transition between configurations. A sequence of transitions starting from the initial configuration are called a computation. A computation halts if it reaches a configuration such that no rules can be applied in any membrane. During a computation, objects can leave the skin membrane and pass to the environment. The result of a halting computation is defined as the number of objects that are sent out of the system during the computation. A nonhalting computation provides no result.


### 3.2. Timed and Time-Free P Systems withd-Division

Given a P system withd-division
(2)Π=(O,H,μ,w1,…,wm,R)
and a mapping e:R→ℕ, it is said that
(3)Π(e)=(O,H,μ,w1,…,wm,R,e)
is a timed P system with d-division such that e:R→ℕ specifies the execution time of each rule of the system.A timed P system withd-division Π(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 t of computation is defined by the period of time that goes from instant t-1 to instant t. If a membrane i contains some rule r from types (a)–(e′′) selected to be executed, execution of such rule takes e(r) time units to complete. Therefore, if the execution is started at instant j, the rule is completed at instant j+e(r) and the resulting objects and membranes become available only at the beginning of step j+e(r)+1.For a given P systems withd-division, by adding different time mappings, we can obtain a family of timed P systems with d-division. The systems obtained, although in the same family, may produce different computation results for having different time mapping. A timed P system with d-division Π(e) is said to be time-free if and only if, for any time mapping e, the system Π(e) produces the same computation result (if any); that is, the execution time of the rules has no influence on the computation result of such systems.Time-free P systems withd-division are particularly interesting because they allow modelling biological phenomena where the execution time of the processes involved can vary unexpectedly. Similarly, a system like that, if implemented, would be robust against environmental changes that could affect, in an unpredicted manner, the execution time of the evolution rules of the system.


### 3.3. Uniform Time-Free Solutions to Decision Problems by Timed P Systems withd-Division

In order to formally define the concept of uniform time-free solution to decision problems by timed P systems (in our case withd-division), following from [9, 13], some notions related to solving decision problems with P systems with d-division are reviewed. It is started by introducing recognizer timed P systems with d-division.A recognizer P system withd-division is the one such that (i) the working alphabet contains two distinguished elements yes and no; (ii) all computations halt; and (iii) if C is a computation of the system, either object yes or object no (but not both) must have been released into the environment when the system halts. The recognizer P systems with d-division can be used to solve decision problems as follows. For an instance γ of the problem X, the computations of the systems start from an initial configuration by adding the code of the problem cod(γ) to the systems. If the computations of the systems finally halt with object yes (no) present in the environment, we say that the problem has a positive (negative) answer. In recognizer P systems with d-division, a computation is said to be accepting (rejecting) if the object yes (no) appears in the environment associated with the corresponding halting configuration.In the following description, we will formally describe the notions of solutions to decision problems by P systems withd-division. Let X=(IX,ΘX) be a decision problem, where IX is a set of instances and ΘX is a predicate over IX, and let Π={Π(n)∣n∈ℕ} be a family of recognizer P systems with d-division. We say that the decision problem X is solvable in polynomial time by a (countable) family of P systems with d-division Π if the following holds.(i)
The familyΠ is polynomial uniform by Turing machine; that is, there exists a deterministic Turing machine constructing the system Π(n) for n∈ℕ in polynomial time.(ii)
There is a pair of polynomial computable functions(cod,s) over the problem X such that
(a)
for each instanceu∈IX, cod(u) is the input of the system Π and s(u)∈ℕ;(b)
the familyΠ is sound with respect to X,cod,s; that is, for each instance of the problem u∈IX if there exists an accepting computation of Π(s(u)) with input cod(u), we have ΘX(u)=1;(c)
the familyΠ is complete with respect to X,cod,s; that is, for each instance of the problem u∈IX if ΘX(u)=1, every computation of Π(s(u)) is an accepting computation;(d)
the familyΠ is polynomial bounded if there exists a polynomial function p such that, for each u∈IX, all computations in Π(s(u)) halt in, at most, p(|u|) steps.The notions of soundness and completeness described above can be extended to timed P systems withd-division, with the exception that the polynomially bounding needs to be reconsidered. In timed P systems with d-division, execution of time of rules is determined by the time mapping e; thus, the existence of rules whose execution time is inherently exponential is possible. Therefore, the polynomial bounded restriction on the computation time cannot be assured any more.To circumvent this, another way to define computation steps in timed P systems is considered, based onrule starting steps (RS steps for short). Hence, although there exists an external clock ticking, marking the time for the system, only those ticks of the clock in which at least one rule starts its execution are considered as the beginning of a computation step. The ticks in which no object “begins” to evolve or no membrane “begins” to change, are omitted from computation steps.With the previous definitions we can then define the concepts of timed soundness, timed completeness and timed polynomially bounding for recognizer timed P systems withd-division. Let Π={Π(n,e)∣n∈ℕ} be a family of timed recognizer P systems with d-division;(e)
the familyΠ is timed sound with respect to X,cod,s; that is, for each instance of the problem u∈IX and a given time mapping e, if there exists an accepting computation of Π(s(u),e) with input cod(u), we have ΘX(u)=1;(f)
the familyΠ is timed complete with respect to X,cod,s; that is, for each instance of the problem u∈IX and a given time mapping e, if ΘX(u)=1, every computation of Π(s(u),e) is an accepting computation;(g)
the familyΠ is timed polynomial bounded if there exists a polynomial function p such that, for each u∈IX and given time mapping e, all computations in Π(s(u),e) halt in, at most, p(|u|) RS-steps.Similarly, we can define the concepts defined above for recognizer time-free P systems withd-division. Let Π={Π(n,e)∣n∈ℕ} be a family of timed recognizer P systems with d-division;(h)
the familyΠ is time-free sound with respect to X,cod,s; that is, for each instance of the problem u∈IX and any time mapping e, if there exists an accepting computation of Π(s(u),e) with input cod(u), then we have ΘX(u)=1;(i)
the familyΠ is time-free complete with respect to X,cod,s; that is, for each instance of the problem u∈IX and any time mapping e, if ΘX(u)=1, every computation of Π(s(u),e) is an accepting computation;(j)
the familyΠ is time-free polynomial bounded if there exists a polynomial function p such that, for each u∈IX and any time mapping e, computations in Π(s(u),e) halt in, at most, p(|u|) RS-steps.Finally, we define the concept of uniform time-free solution to decision problems.LetX=(IX,ΘX) be a decision problem. A family of timed recognizer P systems Π={Π(s(u),e)∣u∈IX} is a uniform time-free solution to decision problem X if the following statements are true:(k)
the familyΠ is polynomially uniform with respect to Turing machines; that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(e) with knowledge involving only the size of the problem X for every instance of X;(l)
The familyΠ is time-free polynomially bounded (halts in a polynomial number of RS-steps);(m)
the familyΠ is time-free sound and time-free complete.Given a decision problemX, if there exists a family of timed P system Π={Π(s(u),e)∣u∈IX} which computes a solution of the instance u of X, and the correctness of the solution does not depend on the execution time of the rules involved in the computation, then the solution is called a time-free solution to problem X computed by the systems Π.


## 3.1. P Systems withd-Division

AP system withd-division (d≥2) of degree m is a construct
(1)Π=(O,H,μ,w1,…,wm,R),where(i)
m≥1 is the initial number of membranes of the system;(ii)
O is the alphabet of objects;(iii)
H is a finite set of labels for membranes;(iv)
μ is the initial membrane structure, consisting of m membranes; membranes are labelled (not necessarily in an injective way) with elements of H and are electrically polarized, being possible charge positive (+), negative (−), or neutral (0);(v)
w1,…,wm are strings over O, describing the initial multisets of objects placed in the m regions of μ;(vi)
R is a finite set of evolution rules, of the following types:
(a)
[a→v]hα, h∈H,α∈{+,-,0},a∈O,v∈O*;(b)
a[]hα1→[b]hα2, h∈H,α1,α2∈{+,-,0},a,b∈O;(c)
[a]hα1→[]hα2b, h∈H,α1,α2∈{+,-,0},a,b∈O;(d)
[a]hα→b, h∈H,α∈{+,-,0},a,b∈O;(e)
[a]hα→[b1]hα1[b2]hα2⋯[bd]hαd,h∈H,α1,α2,…,αd∈{+,-,0},a,b1,b2,…,bd∈O;(f)
[[]h1α1⋯[]hkα1[]hk+1α2⋯[]hnα2]h0α0→[[]h1α3⋯[]hkα3]h0α5[[]hk+1α4⋯[]hnα4]h0α6, k≥1,n>k,hi∈H,0≤i≤n, and α0,…,α6∈{+,-,0} with {α1,α2}={+,-}.Rules of type (a) are objects evolution rules, whose application is controlled by both the label and the charge of the membranes. Rules of type (b) and (c) are communication rules, by which an object can be sent into or out of the membrane. The objects can be possibly modified during this process, as well as the polarization of the membrane can be changed, but not its label. The dissolving rules are of type (d), by which a membrane can be dissolved, while the object specified in the rule can be modified. The division rules for elementary membranes are of type (e). In reaction with an object, the elementary membrane can be divided intod membranes with the same labels, possibly of different polarizations; the object specified in the rule is replaced by some newly generated objects in the newly membranes. As shown in rules of type (f), if a membrane contains other membranes that have charges + or − but have globally neutral charge, these membranes with same charges can be be separated into two new membranes. The previous rules can be considered as “standard” rules; two possible extensions for rules of type (e) can be also considered:(e′)
[a]hα→[b1]h1α1[b2]h2α2⋯[bd]hdαd, h,h1,h2,…hd∈H,α,α1,α2,…,αd∈{+,-,0},a,b1,b2,…,bd∈O,d≥2;(e′′)
[a]hα1→[b1]hα2[b2]hα2⋯[bd]hαd, h∈H,α1,α2,…,αd∈{+,-,0},a,b1,b2,…,bd∈O, d≥2.By rules of type (e′), the membranes produced by division possibly have different labels with the divided membrane, and the polarizations of the new membranes can be different from the polarization of the initial one. Division rules (e′′) allow the division of nonelementary membranes, where all membranes from the initial membranes will be replicated and will appear in the new copies of this membrane.In each time unit (a global clock is assumed, marking the time for the whole system), the selected rules to be executed in each cell are applied on the tick of the clock, taking exactly one time unit to complete their execution. In a given time, if an object can evolve by more than one rules, only one of the rules is nondeterministically selected. All objects and membranes not specified in any executed rule remain unchanged.If a membrane is dissolved, all the objects contained in the region delimited by such membrane are left free in the surrounding region. If in a given computation step a membrane is divided and there are objects in this membrane which can evolve, it is assumed that evolution of objects takes place first; thus, the evolved objects will be present in the divided membranes. Objects that do not evolve are replicated. Thus, rules are applied “bottom-up”; that is, rules in the innermost membrane are applied first and, subsequently, level by level up to the region of the skin membrane. The skin membrane can never divide, but it can be “electrically charged.”Note that every cell in the systems works in a sequential way, in each time unit only one evolution can be used, but, for different cells, they work in a synchronous way.The configuration of the system at a given time unit is described by both the membrane structure and the multisets of objects present in each cell. By applying the rules specified above, one can define a transition between configurations. A sequence of transitions starting from the initial configuration are called a computation. A computation halts if it reaches a configuration such that no rules can be applied in any membrane. During a computation, objects can leave the skin membrane and pass to the environment. The result of a halting computation is defined as the number of objects that are sent out of the system during the computation. A nonhalting computation provides no result.


## 3.2. Timed and Time-Free P Systems withd-Division

Given a P system withd-division
(2)Π=(O,H,μ,w1,…,wm,R)
and a mapping e:R→ℕ, it is said that
(3)Π(e)=(O,H,μ,w1,…,wm,R,e)
is a timed P system with d-division such that e:R→ℕ specifies the execution time of each rule of the system.A timed P system withd-division Π(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 t of computation is defined by the period of time that goes from instant t-1 to instant t. If a membrane i contains some rule r from types (a)–(e′′) selected to be executed, execution of such rule takes e(r) time units to complete. Therefore, if the execution is started at instant j, the rule is completed at instant j+e(r) and the resulting objects and membranes become available only at the beginning of step j+e(r)+1.For a given P systems withd-division, by adding different time mappings, we can obtain a family of timed P systems with d-division. The systems obtained, although in the same family, may produce different computation results for having different time mapping. A timed P system with d-division Π(e) is said to be time-free if and only if, for any time mapping e, the system Π(e) produces the same computation result (if any); that is, the execution time of the rules has no influence on the computation result of such systems.Time-free P systems withd-division are particularly interesting because they allow modelling biological phenomena where the execution time of the processes involved can vary unexpectedly. Similarly, a system like that, if implemented, would be robust against environmental changes that could affect, in an unpredicted manner, the execution time of the evolution rules of the system.


## 3.3. Uniform Time-Free Solutions to Decision Problems by Timed P Systems withd-Division

In order to formally define the concept of uniform time-free solution to decision problems by timed P systems (in our case withd-division), following from [9, 13], some notions related to solving decision problems with P systems with d-division are reviewed. It is started by introducing recognizer timed P systems with d-division.A recognizer P system withd-division is the one such that (i) the working alphabet contains two distinguished elements yes and no; (ii) all computations halt; and (iii) if C is a computation of the system, either object yes or object no (but not both) must have been released into the environment when the system halts. The recognizer P systems with d-division can be used to solve decision problems as follows. For an instance γ of the problem X, the computations of the systems start from an initial configuration by adding the code of the problem cod(γ) to the systems. If the computations of the systems finally halt with object yes (no) present in the environment, we say that the problem has a positive (negative) answer. In recognizer P systems with d-division, a computation is said to be accepting (rejecting) if the object yes (no) appears in the environment associated with the corresponding halting configuration.In the following description, we will formally describe the notions of solutions to decision problems by P systems withd-division. Let X=(IX,ΘX) be a decision problem, where IX is a set of instances and ΘX is a predicate over IX, and let Π={Π(n)∣n∈ℕ} be a family of recognizer P systems with d-division. We say that the decision problem X is solvable in polynomial time by a (countable) family of P systems with d-division Π if the following holds.(i)
The familyΠ is polynomial uniform by Turing machine; that is, there exists a deterministic Turing machine constructing the system Π(n) for n∈ℕ in polynomial time.(ii)
There is a pair of polynomial computable functions(cod,s) over the problem X such that
(a)
for each instanceu∈IX, cod(u) is the input of the system Π and s(u)∈ℕ;(b)
the familyΠ is sound with respect to X,cod,s; that is, for each instance of the problem u∈IX if there exists an accepting computation of Π(s(u)) with input cod(u), we have ΘX(u)=1;(c)
the familyΠ is complete with respect to X,cod,s; that is, for each instance of the problem u∈IX if ΘX(u)=1, every computation of Π(s(u)) is an accepting computation;(d)
the familyΠ is polynomial bounded if there exists a polynomial function p such that, for each u∈IX, all computations in Π(s(u)) halt in, at most, p(|u|) steps.The notions of soundness and completeness described above can be extended to timed P systems withd-division, with the exception that the polynomially bounding needs to be reconsidered. In timed P systems with d-division, execution of time of rules is determined by the time mapping e; thus, the existence of rules whose execution time is inherently exponential is possible. Therefore, the polynomial bounded restriction on the computation time cannot be assured any more.To circumvent this, another way to define computation steps in timed P systems is considered, based onrule starting steps (RS steps for short). Hence, although there exists an external clock ticking, marking the time for the system, only those ticks of the clock in which at least one rule starts its execution are considered as the beginning of a computation step. The ticks in which no object “begins” to evolve or no membrane “begins” to change, are omitted from computation steps.With the previous definitions we can then define the concepts of timed soundness, timed completeness and timed polynomially bounding for recognizer timed P systems withd-division. Let Π={Π(n,e)∣n∈ℕ} be a family of timed recognizer P systems with d-division;(e)
the familyΠ is timed sound with respect to X,cod,s; that is, for each instance of the problem u∈IX and a given time mapping e, if there exists an accepting computation of Π(s(u),e) with input cod(u), we have ΘX(u)=1;(f)
the familyΠ is timed complete with respect to X,cod,s; that is, for each instance of the problem u∈IX and a given time mapping e, if ΘX(u)=1, every computation of Π(s(u),e) is an accepting computation;(g)
the familyΠ is timed polynomial bounded if there exists a polynomial function p such that, for each u∈IX and given time mapping e, all computations in Π(s(u),e) halt in, at most, p(|u|) RS-steps.Similarly, we can define the concepts defined above for recognizer time-free P systems withd-division. Let Π={Π(n,e)∣n∈ℕ} be a family of timed recognizer P systems with d-division;(h)
the familyΠ is time-free sound with respect to X,cod,s; that is, for each instance of the problem u∈IX and any time mapping e, if there exists an accepting computation of Π(s(u),e) with input cod(u), then we have ΘX(u)=1;(i)
the familyΠ is time-free complete with respect to X,cod,s; that is, for each instance of the problem u∈IX and any time mapping e, if ΘX(u)=1, every computation of Π(s(u),e) is an accepting computation;(j)
the familyΠ is time-free polynomial bounded if there exists a polynomial function p such that, for each u∈IX and any time mapping e, computations in Π(s(u),e) halt in, at most, p(|u|) RS-steps.Finally, we define the concept of uniform time-free solution to decision problems.LetX=(IX,ΘX) be a decision problem. A family of timed recognizer P systems Π={Π(s(u),e)∣u∈IX} is a uniform time-free solution to decision problem X if the following statements are true:(k)
the familyΠ is polynomially uniform with respect to Turing machines; that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(e) with knowledge involving only the size of the problem X for every instance of X;(l)
The familyΠ is time-free polynomially bounded (halts in a polynomial number of RS-steps);(m)
the familyΠ is time-free sound and time-free complete.Given a decision problemX, if there exists a family of timed P system Π={Π(s(u),e)∣u∈IX} which computes a solution of the instance u of X, and the correctness of the solution does not depend on the execution time of the rules involved in the computation, then the solution is called a time-free solution to problem X computed by the systems Π.


## 4. A Uniform Time-Free Solution to HPP

In this section, we prove that a family of timed P systems withd-division can solve HPP in polynomial RS-steps, and the systems are constructed in a uniform way. It is noticed that in our systems we extend the number of objects involved in the rules of type (a). Specifically, the extended rules of type (a) are of the form(a′)
[u→v]hα,h∈H,α∈{+,-,0},u,v∈O*,by which a multiset of objects can evolve. After that, we will prove that the correctness of our solution does not depend on the execution time of the rules; that is, for any time mapping e, we will obtain the same answer to the instances of the problems.Hamiltonian Path Problem (HPP) is one of the best known NP-complete problems, which asks whether or not for a given graph γ=(N,E) (N is the set of nodes and E is the set of edges in γ) contains a Hamiltonian path, that is a path of length n that visits all nodes from γ exactly once; we do not specify the first and last nodes of a path, and each node in node set N can be the first node or the last one.Theorem 1.
TheHPP can be solved in polynomial RS steps with respect to the number of nodes of a directed graph by a family of timed P systems with d-division using rules of types (a′), (b), (c), and  (e′).Proof.
Let us consider a directed graphγ=(N,E), where N={v1,v2,…,vn} is the set of vertices and E is the set of edges. We codify γ by multiset cod(γ)=a1a2⋯an, where variable ai represents vertex vi. In this way, we pass from γ to cod(γ) in linear steps with respect to n. The instance γ will be processed by timed P systems with d-division Π(s(γ)) with input cod(γ), where s(γ)=n.
We construct the family of timed P system withd-division of degree 2:
(4)Π(n,e)=(O,H,μ,w0,wp,R,e),where(i)
O={ai∣1≤i≤n}∪{bi∣1≤i≤n}∪{yes,no,c,c′,d,t,t′} is the alphabet, and each object ai corresponds to node vi,1≤i≤n;(ii)
H={0,1,2,…,2n+1,p} is the set of labels of the membranes;(iii)
μ=[[]0]p is the initial membrane structure;(iv)
w0=dcbn-1 and wp=no;(v)
R is the set evolution rules;(vi)
e:R→ℕ is the time mapping for the rules from R.
In what follows, a detailed explanation of how the systemΠ(n,e) computes a solution to HPP is present. Three stages in the computation process are considered: generating, checking, and outputting.
Generating stage:
G
1:
[
no
]
p
→
[
]
p
no,
G
2:
[
d
]
0
→
[
a
1
]
1
[
a
2
]
1
⋯
[
a
n
]
1.
At the beginning of the computation, objectno can be ejected to the environment after e(G1) steps by the rule G1. By using the rule G2, we start to create the paths in γ starting from all the nodes vi,1≤i≤n. This process will be completed in e(G2) time units, costing only one RS step.G3i:
[b]i→[a1]i+1[a2]i+1⋯[an]i+1,1≤i≤n-1.
Prolonging the paths with one node, where all the nodes are assumed to have an edge between each node. For the membrane with same label, the ruleG3i will be used in parallel; thus, for each i, the application of rule G3i costs one RS step to prolong one node to all the nodes:G4i:
[akah→λ]i with 1≤i≤n and k,h∈{1,2,…,n} if there is no edge between node vk and vh.
By using rulesG4i, the objects representing the edges that are not in γ can evolve into empty string (thus are removed out of the systems), and only the objects representing the edges in γ are left in the system. In the worst case, each pair of (vk,vh) is not in E, so the membrane with label i will use at most n2 rules in parallel, so this process will cost at most n2 RS-steps for each i∈{1,2,…,n}. Note that it is assumed that when division rules and evolutions can both be used (in our case it is possible that rules G3i and G4i can be applied at the same time), evolution of objects takes place first; thus, the objects evolved by rule G3i will be present in the divided membranes by rule G4i for any i∈{1,2,…,n}:G5:
[c]n→[c′]n+1[c′]n+1.
Since the length of Hamiltonian path isn, we need to check all the paths in γ with length n. After the application of rules G4i is completed, the membranes with label n containing object c can divide. The generating stage will finish when membranes with label n+1 are generated.
Checking stage:
C
1
i:
[
a
i
]
n
+
i
→
[
a
]
n
+
i
+
1
[
a
]
n
+
i
+
1
with
i
=
1,2
,
…
,
n
-
1,
C
2:
[
a
n
]
2
n
→
[
t
′
]
2
n
+
1
[
t
]
2
n
+
1.
After generating all the possible paths with length not more thann (each in a separated membrane with label n), we need to check whether there exist some paths that contain all the nodes v1,v2,…,vn. This process is started by checking object a1 in the membranes n+1. For each membrane n+1, if it contains object a1, rule C11 can be applied, and after e(C11) steps, membranes with label n+2 are produced. Membranes n+1 without object a1 can not evolve any more, and no further rule can be used over them. After membranes labelled with n+2 are generated, object a2 in the membranes can evolve by using the rule C12, and so forth. The checking stage will cost n RS steps at most (in case there is at least one membrane n+1 that contains all the objects a1,a2,…,an).
If there is no membranen+1 containing all the objects a1,a2,…,an, the checking stage halts and cannot go to outputting stage. There are the following two cases. If the rule G1 has completed its application, that is object no presents in the environment. In this case, we get object no in the environment when system halts; hence, the answer to the decision problem is negative. When the computation of the system halts the application of rule G1 does not complete. In this case, the system halts as soon as the application of rule G1 is finished. We also get object no in the environment, hence the answer of the problem is negative.
If there exists at least one membranen+1 that contains all the objects a1,a2,…,an, the computation proceeds to the outputting stage.
Outputting stage:
O
1:
[
t
]
2
n
+
1
→
[
]
2
n
+
1
0
yes
O
2:
no
[
yes
]
p
→
[
no
]
p
yes.
Membranes with label2n+1 that contains object t will be produced. Object t in membrane 2n+1 can be sent out of the membrane and evolves into object yes. This process costs one RS step. In this way, object yes passes to membrane p. Subsequently, by using rule O2, object yes in membrane p is sent out to the environment and object no goes into membrane p. After that, the system halts with object yes placed in the environment, so the answer to the decision problem is positive.
We can easily check that the presented systemΠ(n,e) can be built in polynomial time with respect to n (the number of nodes in N of γ). Specifically, the necessary resources to build the system Π(n,e) are shown as follows: the size of the alphabet, 2n+7∈O(n); the initial number of cells, 2∈O(1); the initial number of objects, 2n+2∈O(n); and the number of rules (in the most case), n3+2n+4∈O(n3).
Therefore, there exists a deterministic Turing machine working in polynomial time which constructs the system with knowledge only of the number of nodes in the graph; that is, the family of P systems withd-division Π(n,e) is constructed in a uniform way. It is easy to check that the family of systems Π(n,e) are timed sound and timed complete.
In the generating stage, the applications of rulesG1 and G2 cost two RS steps; every membrane i applies rules G3i,1≤i≤n-1 in parallel; thus, n-1 RS-steps are required to start their execution; for any membrane i, the application of rule G4i costs n2 RS steps at most to start their execution, (since in each membrane i, in the worst case it contains all the rules [akah→λ]i with h,k=1,2,…,n); for all the n membranes, totally we need n3 RS-steps for the execution of rules G4i; one RS step is needed to start the execution of rule G5. In the checking stage, it costs at most n RS steps in the case that there exists at least one membrane n+1, contains all the variables a1,a2,…,an. Two RS steps are needed to output the object yes (if any) to the environment. Therefore, n3+2n+4 RS-steps are required at most to complete the computation of Π(n,e), which is polynomial.
As explained above, we can conclude that the family of timed P systemsΠ(n,e) with d-division is a uniform solution to HPP.Corollary 2.
For any time mappinge, by means of the family of P systems with d-division Π(n,e) constructed in Theorem 1, the same solution can be obtained for a given instance of the HPP; that is, the correctness of the solution does not depend on the execution time of the rules.Proof.
It is easy to check that (for any time mappinge) the family of P systems with d-division Π(n,e) constructed in Theorem 1 are time-free sound, time-free complete, and time-free polynomially bounded. Therefore, the solution to HPP by the family of timed P systems with d-division Π(n,e) is time-free.


## 5. Conclusions and Future Work

In this paper, inspired from the biological fact that execution time of biochemical reactions can vary because of external uncontrollable conditions, we consider timed P systems withd-division by adding a time mapping to each evolution rule. In the systems, the general restriction on the constant execution time of the rules as defined in classical P systems is removed. We consider rule starting steps (RS-steps) as “valid” computation steps; that is, only those ticks of the clock in which at least one rule starts its execution are considered as the beginning of a computation step. The ticks, in which no object “begins” to evolve or no membrane “begins” to change, are omitted from computation steps. In this way, we can avoid the inherently possible exponential execution time of the rules in such systems. We investigate the efficiency of timed P systems with d-division. As a result, a time-free uniform solution to HPP is obtained.



---

*Source: 975798-2013-09-14.xml*