# Solving Multidimensional 0-1 Knapsack Problem with Time-Free Tissue P Systems

Authors: Xiangrong Liu; Ziming Li; Juan Suo; Ying Ju; Juan Liu; Xiangxiang Zeng
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Tissue P system is a class of parallel and distributed model; a feature of traditional tissue P system is that the execution time of certain biological processes is very sensitive to environmental factors that might be hard to control. In this work, we construct a family of tissue P systems that works independently from the values associated with the execution times of the rules. Furthermore, we present a time-free efficient solution to multidimensional 0-1 knapsack problem by timed recognizer tissue P systems.


---

## Body

## 1. Introduction

Membrane computing is one of the recent branches of natural computing, which has developed rapidly (already in 2003, ISI considered membrane computing as fast emerging research area in computer science; see http://esi-topics.com/). The aim is to abstract computing ideas (data structures, operations with data, ways to control operations, computing models, etc.) from the structure and the functioning of a single cell and from complexes of cells, such as tissues and organs including the brain. The various types of membrane systems are known as P systems after Păun who first conceived the model in 2000 [1] (the paper was circulated first as a Turku Center for Computer Science (TUCS) Report 208, 1998). There are three main classes of P systems investigated: cell-like P systems [2, 3], tissue-like P systems [4–6], and neural-like P systems [7, 8]. Many variants of these systems have been also investigated during the past years [9–14], and most of them are proved to be computationally universal (equal in power to Turing machines) [8, 15–17]. A series of applications of P systems, in biology [11, 18–22], economics [23], graphics [24, 25], optimization [26–30], fault diagnosis [31], and so forth, were reported. An overview of the field can be found in [32, 33], with up-to-date information available at the membrane computing website (http://ppage.psystems.eu/).Tissue P systems are inspired from the cell intercommunication in tissues [4], where the membranes are placed in the nodes of a graph and all of the membranes are at the same level. In such a framework, intercellular communication is mainly through the protein channels established among the membranes of the neighboring cells and the membrane structure did not change along the computation. Tissue P systems with cell division rules of the same form as in P systems with active membranes (without using polarizations) were introduced by Păun et al. in 2008 [34]. This kind of systems can generate exponential workspace in linear time by trading space for time. Thus, it provides the possibility of solving NP-hard problems in polynomial or even linear time.A feature of traditional tissue P systems is that each rule is executed in exactly one time unit, but this feature does not have a counterpart in cell biology. In cell biology, the execution time of a reaction is difficult to know precisely and the execution time of certain biological processes is very sensitive to environmental factors that might be hard to control. Therefore, there is a need to construct tissue P systems that work independently from the values associated with the execution time of the rules. Tissue P systems with a time mapping (called timed tissue P systems) can specify the execution time of each rule. A timed tissue P system that generates the same results, independently from the time mapping, is called time-free tissue P system. The concept of time-free was first introduced in [35]. In [36], a time-free solution to Hamilton Path Problems using cell-like P systems was investigated. In this work, we construct a family of time-free tissue P systems to solve another well-known NP-complete problem: the multidimensional 0-1 knapsack problem.This paper is organized as follows. Firstly, we recall the definition of tissue P systems. Then, we introduce timed tissue P systems with cell division. Finally, a uniform time-free solution for multidimensional 0-1 knapsack problem is proposed, and the informal verification of the solution is presented.


## 2. Tissue P Systems with Cell Division

It is useful for readers to have some familiarity with (basic elements of) language theory, for example, from [37], as well as basic membrane computing [32]. In what follows we briefly recall some concepts of formal language theory used later in this paper.For an alphabetV, V
* denotes the set of all strings (ordered finite sequences) 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 an 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
=
{
a
1
,
a
2
,
…
,
a
n
} is finite, a multiset M over U, represented by the set of mappings {
(
a
1
,
M
(
a
1
)
)
,
(
a
2
,
M
(
a
2
)
)
,
…
,
(
a
n
,
M
(
a
n
)
)
} can also be represented by a string w
=
a
1
M
(
a
1
)
a
2
M
(
a
2
)
⋯
a
n
M
(
a
n
) or by any of its permutations. We denote by M
(
U
) the set of all multisets over U. In [34], Păun et al. presented a new model of tissue P systems with cell division. The biological inspiration is that alive tissues are not static network of cells, since cells are duplicated via mitosis in a natural way.Formally, atissue P system with cell division of degree q
≥
1 is a tuple of the form [34]
(1)
Π
=
(
Γ
,
Ω
,
w
1
,
…
,
w
q
,
R
,
i
out
)
,
where(1)
q
≥
1 is the initial degree of the system, which means the system contains q cells labeled with 1,2
,
…
,
q, respectively. We use 0 to refer to the environment;
(2)
Γ is thealphabet ofobjects;
(3)
w
1
,
…
,
w
q are multisets over Γ, describing the objects placed in the cells of the system at the beginning of the computation;
(4)
Ω
⊆
Γ is the set of objects initially located in the environment of the system, all of them available in an arbitrary number of copies;
(5)
R is a finite set of rules of the following forms:
(a)
communication rules: (
i
,
u
/
v
,
j
), for i
,
j
∈
{
0,1
,
2
,
…
,
q
}, i
≠
j, i
≠
i
out, u
,
v
∈
M
(
Γ
)(|
u
|
+
|
v
| is called the length of the communication rule (
i
,
u
/
v
,
j
));
(b)
division rules: [
a
]
i
→
[
b
]
i
[
c
]
i, where i
∈
{
1
,
…
,
q
}, i
≠
i
out, a
∈
Γ, and b
,
c
∈
Γ
∪
{
λ
};
(6)
i
out
∈
{
0,1
,
2
,
…
,
q
} is the output cell if i
out
≠
0 or the environment if i
out
=
0.Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way. In each step, all cells which can evolve must evolve in a maximally parallel way (in each step we apply a multiset of rules which is maximal, no further rule can be added), with the following important mentioning: if a cell is divided, then the division rule is the only one which is applied for that cell in that step, its objects do not evolve by means of communication rules. Their labels precisely identify the rules which can be applied to them.The communication rule(
i
,
u
/
v
,
j
) can be applied over two cells i and j such that u is contained in cell i and v is contained in cell j. When applying a rule (
i
,
u
/
v
,
j
), the objects of the multiset represented by u are sent from cell i to cell j and simultaneously the objects of the multiset v are sent from cell j to cell i.The division rule[
a
]
i
→
[
b
]
i
[
c
]
i can be applied over a cell i containing object a. When applying a rule [
a
]
i
→
[
b
]
i
[
c
]
i, the cell with label i is divided into two cells with the same label; in the first copy the object a is replaced by b, in the second copy the object a is replaced by c; all other objects are replicated and copies of them are placed in the two new cells.A configuration ofΠ at an instant t is described by the multisets of objects over Γ associated with all the cells present in the system at the moment and the multiset over Γ
∖
Ω associated with the environment at the instant t. The computation starts from the initial configuration and proceeds as defined above; only halting computations give a result, and the result is encoded (usually by the number of objects) in the output region i
out (a cell if i
out
∈
{
1
,
…
q
} or the environment if i
out
=
0) in the halting configuration. The set of numbers computed in this way by the various halting computations in Π is denoted by N
(
Π
).


## 3. Timed Tissue P Systems with Cell Division

A timed tissue P system can be constructed by adding to the tissue P system a time mappinge
:
R
→
ℕ
∖
{
0
}, which specifies the execution time of each rule of the system. We suppose to have an external clock (that does not have any influence on the system) that marks time units of equal length, starting from time 0. In each step of the rules, all cells which can evolve must evolve in a maximally parallel way. There is a need to define the concept of a valid step. If in one step there exists at least one rule of system Π
(
e
) which can start, we say that the step isvalid. The execution of the rules does not take the same time unit. When a rule r is started, the occurrences of objects used by this rule are not available for other rules during the entire execution of r. We denote e
(
r
) as the time which rule r lasts, that is, execution of rule r takes e
(
r
) time units to be completed. The computation stops when no rule can be applied in any membrane and there are no rules in execution (the systems has reached a halting configuration). The output of a halting computation is always defined based on the objects in the output membrane in the halting configuration.We can construct a family of timed tissue P systems by adding different time mappings. The same family of tissue P systems may produce different results for having different time mappings. A timed tissue P system that generates the same computation result, independently from any time mapping, is called time-free tissue P system.


### 3.1. A Timed Recognizer Tissue P System

In this subsection, we introduce a variant of timed tissue P systems with cell division, namely, timed recognizer tissue P system following the definitions of complexity classes in terms of membrane computing (see [38]). Such a system of degree q
≥
1 has the form
(2)
Π
(
e
)
=
(
Γ
,
Σ
,
Ω
,
w
1
,
…
,
w
q
,
R
,
i
in
,
i
out
,
e
)
.
There are two points that should be noted. First, the working alphabet Γ has two distinguished objectsyes andno, present in at least one copy in some initial multisets w
1
,
…
,
w
q but not present in Ω. Second, if 𝒞 is a computation of Π, then either the objectyes or the objectno (but not both) must exist in the environment when the computation halts.The computations of the systemΠ with input multiset w
∈
M
(
Γ
) start from a configuration of the form (
w
1
,
w
2
,
…
,
w
in
w
,
…
,
w
q
,
∅
), that is, after adding the multiset w to the contents of the input cell i
in. We say that the multiset w is recognized by Π if and only if the objectyes is sent to the environment, and only at the last step of the corresponding computation. We say that 𝒞 is an accepting computation (resp., rejecting computation) if the objectyes (resp.,no) appears in the environment associated with the corresponding halting configuration of 𝒞.Next, we will define the concepts of time-free soundness, time-free completeness, and time-free polynomially bounding for timed recognizer tissue P systems. Let∏
‍
=
{
Π
(
n
,
e
)
∣
n
∈
ℕ
} be a family of timed recognizer tissue P systems. There exists a pair (
cod
,
s
) of polynomial-time computable functions over X such that(i)
for each instanceu
∈
I
x, s
(
u
) is a natural number and cod
(
u
) is an input multiset of the system Π
(
s
(
u
)
);
(ii)
the family∏
‍ istime-free sound with regard to (
X
,
cod
,
s
); that is, for each instance of the problem u
∈
I
x and any mapping e, if there exists an accepting computation of the time-free system Π
(
s
(
u
)
,
e
) (this means Π
(
s
(
u
)
)
(
e
)) with input cod
(
u
), then we have Θ
x
(
u
)
=
1;
(iii)
the family∏
‍ istime-free complete with regard to (
X
,
cod
,
s
); that is, for each u
∈
I
x and any mapping e, if Θ
x
=
1, then every computation of Π
(
s
(
u
)
,
e
) with input cod
(
u
) is an accepting one;
(iv)
the family∏
‍ istime-free polynomial bounded with regard to (
X
,
cod
,
s
), that is, there exists a polynomial function p, such that for each u
∈
I
x and any time mapping e, every computation of the time-free system Π
(
s
(
u
)
,
e
) with input cod
(
u
) is halting and, moreover, it performs at most p
(
|
u
|
) steps.A family∏
‍
=
{
Π
(
s
(
u
)
,
e
)
∣
u
∈
I
x
} of timed recognizer tissue P systems is a uniform time-free solution to decision problem X
=
(
I
X
,
θ
X
) if the following holds:(i)
the family∏
‍ ispolynomially uniform by 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;
(ii)
the family∏
‍ is time-free polynomially bounded, time-free sound, and time-free complete.Given a decision problemX, if there exists a family of timed P system ∏
‍
=
{
Π
(
s
(
u
)
,
e
)
∣
u
∈
I
x
} 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 system ∏.


## 3.1. A Timed Recognizer Tissue P System

In this subsection, we introduce a variant of timed tissue P systems with cell division, namely, timed recognizer tissue P system following the definitions of complexity classes in terms of membrane computing (see [38]). Such a system of degree q
≥
1 has the form
(2)
Π
(
e
)
=
(
Γ
,
Σ
,
Ω
,
w
1
,
…
,
w
q
,
R
,
i
in
,
i
out
,
e
)
.
There are two points that should be noted. First, the working alphabet Γ has two distinguished objectsyes andno, present in at least one copy in some initial multisets w
1
,
…
,
w
q but not present in Ω. Second, if 𝒞 is a computation of Π, then either the objectyes or the objectno (but not both) must exist in the environment when the computation halts.The computations of the systemΠ with input multiset w
∈
M
(
Γ
) start from a configuration of the form (
w
1
,
w
2
,
…
,
w
in
w
,
…
,
w
q
,
∅
), that is, after adding the multiset w to the contents of the input cell i
in. We say that the multiset w is recognized by Π if and only if the objectyes is sent to the environment, and only at the last step of the corresponding computation. We say that 𝒞 is an accepting computation (resp., rejecting computation) if the objectyes (resp.,no) appears in the environment associated with the corresponding halting configuration of 𝒞.Next, we will define the concepts of time-free soundness, time-free completeness, and time-free polynomially bounding for timed recognizer tissue P systems. Let∏
‍
=
{
Π
(
n
,
e
)
∣
n
∈
ℕ
} be a family of timed recognizer tissue P systems. There exists a pair (
cod
,
s
) of polynomial-time computable functions over X such that(i)
for each instanceu
∈
I
x, s
(
u
) is a natural number and cod
(
u
) is an input multiset of the system Π
(
s
(
u
)
);
(ii)
the family∏
‍ istime-free sound with regard to (
X
,
cod
,
s
); that is, for each instance of the problem u
∈
I
x and any mapping e, if there exists an accepting computation of the time-free system Π
(
s
(
u
)
,
e
) (this means Π
(
s
(
u
)
)
(
e
)) with input cod
(
u
), then we have Θ
x
(
u
)
=
1;
(iii)
the family∏
‍ istime-free complete with regard to (
X
,
cod
,
s
); that is, for each u
∈
I
x and any mapping e, if Θ
x
=
1, then every computation of Π
(
s
(
u
)
,
e
) with input cod
(
u
) is an accepting one;
(iv)
the family∏
‍ istime-free polynomial bounded with regard to (
X
,
cod
,
s
), that is, there exists a polynomial function p, such that for each u
∈
I
x and any time mapping e, every computation of the time-free system Π
(
s
(
u
)
,
e
) with input cod
(
u
) is halting and, moreover, it performs at most p
(
|
u
|
) steps.A family∏
‍
=
{
Π
(
s
(
u
)
,
e
)
∣
u
∈
I
x
} of timed recognizer tissue P systems is a uniform time-free solution to decision problem X
=
(
I
X
,
θ
X
) if the following holds:(i)
the family∏
‍ ispolynomially uniform by 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;
(ii)
the family∏
‍ is time-free polynomially bounded, time-free sound, and time-free complete.Given a decision problemX, if there exists a family of timed P system ∏
‍
=
{
Π
(
s
(
u
)
,
e
)
∣
u
∈
I
x
} 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 system ∏.


## 4. Solving Multidimensional 0-1 Knapsack Problem by Time-Free Recognizer Tissue P Systems

### 4.1. Problem Formulation

Themultidimensional 0-1 knapsack problem (MKP) is a well-known NP-complete combinatorial problem [39]. The decision MKP can be formulated as follows: given an integer k, an objective function f
(
x
1
,
…
,
x
n
)
=
Σ
i
=
1
n
c
i
x
i, and constraints Σ
i
=
1
n
w
i
j
x
i
≤
b
j, for j
=
1
,
…
,
m, x
i
∈
{
0,1
}, for i
=
1
,
…
,
n, where c
i, w
i
j, and b
j are nonnegative integers, decide whether or not there exists an assignment of variables x
i such that it satisfies the constraints and the objective function is greater than or equal to k.The special case of MKP withm
=
1 is the classical knapsack problem (KP). In [40], a solution to MKP by recognizer P systems with active membranes has been proposed. In the next subsection, we will construct a uniform time-free tissue P system for the general MKP.


### 4.2. A Uniform Time-Free Solution to MKP

We present a uniform time-free solution to MKP in the framework of timed recognizer tissue P systems.Let us consider an instance of MKP as shown in the above subsection, we callΣ
i
=
1
n
w
i
j
x
i
≤
b
j (1
≤
j
≤
m) the jth constraint inequality and Σ
i
=
1
n
c
i
x
i
≥
k the (
m
+
1
)th inequality. We construct a family of timed recognizer tissue P system of degree 2
(3)
Π
(
〈
n
,
m
〉
,
e
)
=
(
Γ
,
Ω
,
w
1
,
w
2
,
R
,
i
in
,
i
out
,
e
)
,
where(i)
Γ
=
{
X
i
,
Y
i
,
N
i
∣
1
≤
i
≤
n
}
∪
{
a
i
j
h
∣
1
≤
i
≤
n
,
1
≤
j
≤
m
,
1
≤
h
≤
w
i
j (only when w
i
j
≥
1
)
}
∪  {
b
l
j
∣
1
≤
j
≤
m
,
0
≤
l
≤
b
j
+
1
}
∪
{
c
i
h
∣
1
≤
i
≤
n
,
1
≤
h
≤
c
i
}
∪
{
k
s
∣
0
≤
s
≤
k
}
∪
{
p
1
,
p
2
,
p
3
,
yes
,
no
};
(ii)
Ω
=
Γ
-
{
yes
,
no
};
(iii)
w
1
=
{
yes
,
no
}, w
2
=
{
X
1
,
…
,
X
n
,
p
1
,
p
2
}
∪
{
a
i
j
h
∣
1
≤
i
≤
n
,
1
≤
j
≤
m
,
1
≤
h
≤
w
i
j
}
∪
{
c
i
h
∣  1
≤
i
≤
n
,
1
≤
h
≤
c
i
}
∪
{
b
0
j
,
k
0
∣
1
≤
j
≤
m
};
(iv)
i
in
=
2 is the input cell;
(v)
the output regioni
out is the environment;
(vi)
e
:
R
→
ℕ is a time mapping from R to natural numbers;
(vii)
R is the set of rules:
(1)
r
1
,
i
≡
[
X
i
]
2
→
[
Y
i
]
2
[
N
i
]
2, for 1
≤
i
≤
n;
(2)
r
2
≡
(
1
,
no
/
λ
,
0
);
(3)
r
3
,
i
j
h
l
≡
(
2
,
Y
i
a
i
j
h
b
l
j
/
Y
i
b
l
+
1
j
,
0
), for 1
≤
i
≤
n, 1
≤
j
≤
m, 1
≤
h
≤
w
i
j (only when w
i
j
≥
1), 0
≤
l
≤
b
j;
(4)
r
4
,
i
h
s
≡
(
2
,
Y
i
c
i
h
k
s
/
Y
i
k
s
+
1
,
0
), for 1
≤
i
≤
n, 1
≤
h
≤
c
i, 0
≤
s
≤
k
-
1;
(5)
r
5
,
j
≡
(
2
,
b
b
j
+
1
j
p
j
/
λ
,
0
), for 1
≤
j
≤
m;
(6)
r
6
≡
(
2
,
k
k
/
p
m
+
1
,
0
);
(7)
r
7
≡
(
2
,
p
1
p
2
⋯
p
m
+
1
/
yes
,
1
);
(8)
r
8
≡
(
2
,
yes
/
no
,
0
).In what follows, a detailed explanation of how this systemΠ
(
〈
n
,
m
〉
,
e
) works to MKP is presented. There are three stages in the computation process: generating, checking, and outputting.In the generating stage, rulesr
1
,
i and r
2 start at the same time. By using the rule r
1
,
i, the system generates 2
n membranes labeled by 2 after e
(
r
1
,
i
) time units. It takes n valid steps to complete rule r
1
,
i. When the generating stage is ended, every membrane labeled by 2 represents one assignment of variables x. Object Y
i means that x
i
=
1, and N
i means 0. Object n
o can be ejected to the environment after e
(
r
2
) steps by the rule r
2.In the checking stage, the rulesr
3
,
i
j
h
l, r
4
,
i
h
s, r
5
,
j, and r
6 are started in the same time and in the nondeterministic maximally parallel manner. Let us explain how these rules work. The rule r
3
,
i
j
h
l means that if Y
i is in one membrane with label 2, object a
i
j
h will be sent to the environment. The range of subscript h is from 0 to w
i
j (the case of w
i
j
=
0 does not have any influence on the systems) and the subscript j means the jth constraint. In the same time, object b
l
j is replaced by object b
l
+
1
j. Rule r
3
,
i
j
h
l will stop when there are no objects a
i
j
h in all the membranes with label 2 or there are no objects b
l
j in the environment. The rule r
3
,
i
j
h
l is used to check the jth constraint inequality Σ
i
=
1
n
w
i
j
x
i
≤
b
j (1
≤
j
≤
m). Similarly, the rule r
4
,
i
h
s is in charge of the checking of the (
m
+
1
)th inequality Σ
i
=
1
n
c
i
x
i
≥
k. If there appears object b
b
j
+
1
j in the membrane, the jth constraint inequality Σ
i
=
1
n
w
i
j
x
i
≤
b
j (1
≤
j
≤
m) is not satisfied and object p
j will be sent to the environment by using rule r
5
,
j. On the contrary, the rule r
6 means that if there exists object k
k, the (
m
+
1
)th inequality is satisfied and object p
m
+
1 will be sent to the membrane.In the last stage, outputting stage, rulesr
7 and r
8 are used to send the right answer to the environment. After checking stage, if objects p
1
,
…
,
p
m
+
1 are all in the membrane, we can come to a conclusion that the assignment of variables x in this membrane satisfies the constraints and the objective function is greater than or equal to k. By using rule r
7, objects p
1
,
…
,
p
m
+
1 are replaced by object y
e
s. This process needs one valid step. By using rule r
8, object y
e
s will be sent to the environment to exchange for object n
o. The system halts with object y
e
s in the environment, which means that the answer to the decision problem is positive. On the contrary, if some of the objects p
j (1
≤
j
≤
m
+
1) are not in the membrane, it means that this assignment of x does not meet the requirements and object y
e
s will remain in the membrane labeled by 1, object n
o will exist in the environment when the computation halts. In this case, the answer to the decision problem is negative.


### 4.3.  Verification

Next, we prove that the family of timed recognizer tissue P systems built above is a uniform time-free solution to MKP.First, according to the definition of uniform time-free solution, we need to show that the familyΠ
(
〈
n
,
m
〉
,
e
) is polynomially uniform by deterministic Turing machines. It is easy to check that the rules of the system Π
(
〈
n
,
m
〉
,
e
) of the family are defined recursively from the values n and m. Besides, the necessary resources to build an element of the family are of a polynomial order, as shown below.(i)
Size of the alphabet:3
n
+
Σ
j
=
1
m
Σ
i
=
1
n
w
i
j
+
Σ
i
=
1
n
c
i
+
Σ
j
=
1
m
b
j
+
3
m
+
k
+
4
∈
Θ
(
n
m
).
(ii)
Initial number of cells:2
∈
Θ
(
1
).
(iii)
Initial number of objects:n
+
Σ
j
=
1
m
Σ
i
=
1
n
w
i
j
+
Σ
i
=
1
n
c
i
+
m
+
5
∈
Θ
(
n
m
).
(iv)
Number of rules:n
+
Σ
j
=
1
m
Σ
i
=
1
n
w
i
j
b
j
+
k
Σ
i
=
1
n
c
i
+
m
+
4
∈
Θ
(
n
m
).
(v)
Number of execution time associated with rules:n
+
Σ
j
=
1
m
Σ
i
=
1
n
w
i
j
b
j
+
k
Σ
i
=
1
n
c
i
+
m
+
4
∈
Θ
(
n
m
).
(vi)
Maximal length of a rule:5
∈
Θ
(
1
).Therefore, a deterministic Turing machine can build Π
(
〈
n
,
m
〉
,
e
) in a polynomial time with respect to n and m.It is clear that the family of timed tissue P systems constructed above is time-free sound, time-free complete, and time-free polynomially bounded. And the total number of valid steps to complete the whole computation process is no more thann
+
Max
⁡
{
k
+
1
,
b
j
+
2
∣
1
≤
j
≤
m
}
+
2. From all the above we have the following result.Theorem 1.
A family of timed tissue P system∏
‍
=
{
Π
(
s
(
u
)
,
e
)
∣
u
∈
I
x
} can be constructed as a uniform time-free solution to multidimensional 0-1 knapsack problem. For any time mapping e, the correctness of the solution does not depend on the execution time of the rules.


## 4.1. Problem Formulation

Themultidimensional 0-1 knapsack problem (MKP) is a well-known NP-complete combinatorial problem [39]. The decision MKP can be formulated as follows: given an integer k, an objective function f
(
x
1
,
…
,
x
n
)
=
Σ
i
=
1
n
c
i
x
i, and constraints Σ
i
=
1
n
w
i
j
x
i
≤
b
j, for j
=
1
,
…
,
m, x
i
∈
{
0,1
}, for i
=
1
,
…
,
n, where c
i, w
i
j, and b
j are nonnegative integers, decide whether or not there exists an assignment of variables x
i such that it satisfies the constraints and the objective function is greater than or equal to k.The special case of MKP withm
=
1 is the classical knapsack problem (KP). In [40], a solution to MKP by recognizer P systems with active membranes has been proposed. In the next subsection, we will construct a uniform time-free tissue P system for the general MKP.


## 4.2. A Uniform Time-Free Solution to MKP

We present a uniform time-free solution to MKP in the framework of timed recognizer tissue P systems.Let us consider an instance of MKP as shown in the above subsection, we callΣ
i
=
1
n
w
i
j
x
i
≤
b
j (1
≤
j
≤
m) the jth constraint inequality and Σ
i
=
1
n
c
i
x
i
≥
k the (
m
+
1
)th inequality. We construct a family of timed recognizer tissue P system of degree 2
(3)
Π
(
〈
n
,
m
〉
,
e
)
=
(
Γ
,
Ω
,
w
1
,
w
2
,
R
,
i
in
,
i
out
,
e
)
,
where(i)
Γ
=
{
X
i
,
Y
i
,
N
i
∣
1
≤
i
≤
n
}
∪
{
a
i
j
h
∣
1
≤
i
≤
n
,
1
≤
j
≤
m
,
1
≤
h
≤
w
i
j (only when w
i
j
≥
1
)
}
∪  {
b
l
j
∣
1
≤
j
≤
m
,
0
≤
l
≤
b
j
+
1
}
∪
{
c
i
h
∣
1
≤
i
≤
n
,
1
≤
h
≤
c
i
}
∪
{
k
s
∣
0
≤
s
≤
k
}
∪
{
p
1
,
p
2
,
p
3
,
yes
,
no
};
(ii)
Ω
=
Γ
-
{
yes
,
no
};
(iii)
w
1
=
{
yes
,
no
}, w
2
=
{
X
1
,
…
,
X
n
,
p
1
,
p
2
}
∪
{
a
i
j
h
∣
1
≤
i
≤
n
,
1
≤
j
≤
m
,
1
≤
h
≤
w
i
j
}
∪
{
c
i
h
∣  1
≤
i
≤
n
,
1
≤
h
≤
c
i
}
∪
{
b
0
j
,
k
0
∣
1
≤
j
≤
m
};
(iv)
i
in
=
2 is the input cell;
(v)
the output regioni
out is the environment;
(vi)
e
:
R
→
ℕ is a time mapping from R to natural numbers;
(vii)
R is the set of rules:
(1)
r
1
,
i
≡
[
X
i
]
2
→
[
Y
i
]
2
[
N
i
]
2, for 1
≤
i
≤
n;
(2)
r
2
≡
(
1
,
no
/
λ
,
0
);
(3)
r
3
,
i
j
h
l
≡
(
2
,
Y
i
a
i
j
h
b
l
j
/
Y
i
b
l
+
1
j
,
0
), for 1
≤
i
≤
n, 1
≤
j
≤
m, 1
≤
h
≤
w
i
j (only when w
i
j
≥
1), 0
≤
l
≤
b
j;
(4)
r
4
,
i
h
s
≡
(
2
,
Y
i
c
i
h
k
s
/
Y
i
k
s
+
1
,
0
), for 1
≤
i
≤
n, 1
≤
h
≤
c
i, 0
≤
s
≤
k
-
1;
(5)
r
5
,
j
≡
(
2
,
b
b
j
+
1
j
p
j
/
λ
,
0
), for 1
≤
j
≤
m;
(6)
r
6
≡
(
2
,
k
k
/
p
m
+
1
,
0
);
(7)
r
7
≡
(
2
,
p
1
p
2
⋯
p
m
+
1
/
yes
,
1
);
(8)
r
8
≡
(
2
,
yes
/
no
,
0
).In what follows, a detailed explanation of how this systemΠ
(
〈
n
,
m
〉
,
e
) works to MKP is presented. There are three stages in the computation process: generating, checking, and outputting.In the generating stage, rulesr
1
,
i and r
2 start at the same time. By using the rule r
1
,
i, the system generates 2
n membranes labeled by 2 after e
(
r
1
,
i
) time units. It takes n valid steps to complete rule r
1
,
i. When the generating stage is ended, every membrane labeled by 2 represents one assignment of variables x. Object Y
i means that x
i
=
1, and N
i means 0. Object n
o can be ejected to the environment after e
(
r
2
) steps by the rule r
2.In the checking stage, the rulesr
3
,
i
j
h
l, r
4
,
i
h
s, r
5
,
j, and r
6 are started in the same time and in the nondeterministic maximally parallel manner. Let us explain how these rules work. The rule r
3
,
i
j
h
l means that if Y
i is in one membrane with label 2, object a
i
j
h will be sent to the environment. The range of subscript h is from 0 to w
i
j (the case of w
i
j
=
0 does not have any influence on the systems) and the subscript j means the jth constraint. In the same time, object b
l
j is replaced by object b
l
+
1
j. Rule r
3
,
i
j
h
l will stop when there are no objects a
i
j
h in all the membranes with label 2 or there are no objects b
l
j in the environment. The rule r
3
,
i
j
h
l is used to check the jth constraint inequality Σ
i
=
1
n
w
i
j
x
i
≤
b
j (1
≤
j
≤
m). Similarly, the rule r
4
,
i
h
s is in charge of the checking of the (
m
+
1
)th inequality Σ
i
=
1
n
c
i
x
i
≥
k. If there appears object b
b
j
+
1
j in the membrane, the jth constraint inequality Σ
i
=
1
n
w
i
j
x
i
≤
b
j (1
≤
j
≤
m) is not satisfied and object p
j will be sent to the environment by using rule r
5
,
j. On the contrary, the rule r
6 means that if there exists object k
k, the (
m
+
1
)th inequality is satisfied and object p
m
+
1 will be sent to the membrane.In the last stage, outputting stage, rulesr
7 and r
8 are used to send the right answer to the environment. After checking stage, if objects p
1
,
…
,
p
m
+
1 are all in the membrane, we can come to a conclusion that the assignment of variables x in this membrane satisfies the constraints and the objective function is greater than or equal to k. By using rule r
7, objects p
1
,
…
,
p
m
+
1 are replaced by object y
e
s. This process needs one valid step. By using rule r
8, object y
e
s will be sent to the environment to exchange for object n
o. The system halts with object y
e
s in the environment, which means that the answer to the decision problem is positive. On the contrary, if some of the objects p
j (1
≤
j
≤
m
+
1) are not in the membrane, it means that this assignment of x does not meet the requirements and object y
e
s will remain in the membrane labeled by 1, object n
o will exist in the environment when the computation halts. In this case, the answer to the decision problem is negative.


## 4.3.  Verification

Next, we prove that the family of timed recognizer tissue P systems built above is a uniform time-free solution to MKP.First, according to the definition of uniform time-free solution, we need to show that the familyΠ
(
〈
n
,
m
〉
,
e
) is polynomially uniform by deterministic Turing machines. It is easy to check that the rules of the system Π
(
〈
n
,
m
〉
,
e
) of the family are defined recursively from the values n and m. Besides, the necessary resources to build an element of the family are of a polynomial order, as shown below.(i)
Size of the alphabet:3
n
+
Σ
j
=
1
m
Σ
i
=
1
n
w
i
j
+
Σ
i
=
1
n
c
i
+
Σ
j
=
1
m
b
j
+
3
m
+
k
+
4
∈
Θ
(
n
m
).
(ii)
Initial number of cells:2
∈
Θ
(
1
).
(iii)
Initial number of objects:n
+
Σ
j
=
1
m
Σ
i
=
1
n
w
i
j
+
Σ
i
=
1
n
c
i
+
m
+
5
∈
Θ
(
n
m
).
(iv)
Number of rules:n
+
Σ
j
=
1
m
Σ
i
=
1
n
w
i
j
b
j
+
k
Σ
i
=
1
n
c
i
+
m
+
4
∈
Θ
(
n
m
).
(v)
Number of execution time associated with rules:n
+
Σ
j
=
1
m
Σ
i
=
1
n
w
i
j
b
j
+
k
Σ
i
=
1
n
c
i
+
m
+
4
∈
Θ
(
n
m
).
(vi)
Maximal length of a rule:5
∈
Θ
(
1
).Therefore, a deterministic Turing machine can build Π
(
〈
n
,
m
〉
,
e
) in a polynomial time with respect to n and m.It is clear that the family of timed tissue P systems constructed above is time-free sound, time-free complete, and time-free polynomially bounded. And the total number of valid steps to complete the whole computation process is no more thann
+
Max
⁡
{
k
+
1
,
b
j
+
2
∣
1
≤
j
≤
m
}
+
2. From all the above we have the following result.Theorem 1.
A family of timed tissue P system∏
‍
=
{
Π
(
s
(
u
)
,
e
)
∣
u
∈
I
x
} can be constructed as a uniform time-free solution to multidimensional 0-1 knapsack problem. For any time mapping e, the correctness of the solution does not depend on the execution time of the rules.


## 5. Conclusions and Remarks

In this paper, we have proposed a time-free solution to a NP-complete problem, the multidimensional 0-1 knapsack problem. The feature of time-free tissue P systems is that they can work independently from the values associated with the execution times of the rules. The solution above can be used as a scheme for designing solutions to other NP-complete problems by a space-time trade off strategy. In the future work, we will give direct time-free solutions to other NP-complete problems or even PSPACE-problems.



---

*Source: 372768-2014-03-27.xml*