Trading Space for Time
In Subsection 2.3.11, we mentioned that many practical problems are intractable for normal computers, and that the parallelism is a possible way to cope with this situation. One of the main features of membrane systems is their inherent parallelism. Can t
- PDF / 6,049,480 Bytes
- 58 Pages / 439.32 x 666.12 pts Page_size
- 74 Downloads / 211 Views
In Subsection 2.3.11, we mentioned that many practical problems are intractable for normal computers, and that the parallelism is a possible way to cope with this situation. One of the main features of membrane systems is their inherent parallelism. Can this parallelism be used for solving ~ in theory ~ hard problems in a feasible time? The answer is positive, and we will illustrate it for various classes of P systems (with enhanced parallelism), which will be shown to be able to solve NP-complete problems in polynomial (often, linear) time. In order to have a systematic framework for assessing the quality of such a solution to a given problem, we start by introducing some new complexity classes, which seem to be appropriate to the membrane computing area.
7.1 Complexity Classes for Membrane Systems For membrane computing the class NC, presented at the end of Subsection 2.3.11 as the best known complexity class for parallel computing, is not very adequate ~ actually, no complexity class mentioned in Subsection 2.3.11 is adequate for membrane computing. The classes P, NP, as well other classes, such as PSPACE, NPSPACE, deal with sequential computing models, while membrane systems are inherently parallel. NC refers to computing models with a structure given in advance, while the membrane systems evolve during the computation; in some sense, the computation essentially means changing the computing device while solving the problem. Moreover, in membrane computing we have possibilities to exponentially increase the workspace, by operations such as cell division, string replication, membrane creation. All these are idealized operations, but they correspond to very precise real phenomena from biology. That is why the definition of NC does not cover our case, and that is why we propose new complexity classes here, related to the way the membrane systems work. Let f be a function from N to N, acceptable from the complexity theory point of view (see Subsection 2.3.11). Actually, here we will consider only the linear functions and the polynomial functions. Let X be a given class of membrane systems, and A be a decidability problem, with answers "yes" and "no". Denote by A(n) the instance of size n of A. G. Păun, Membrane Computing © Springer-Verlag Berlin Heidelberg 2002
272
Trading Space for Time
We say that problem A belongs to MCx(l) if a family of membrane systems IIA = (IIA(I), IIA(2), ... ) of type X exists such that: 1. IIA is a uniform family: there is a Turing machine which constructs IIA (n) in polynomial time starting from A(n). As a direct consequence of the fact that IIA (n) is constructed in polynomial time we have the fact that IIA(n) has a polynomial size: the size of IIA(n) (for example, the total number of symbols necessary to encode IIA (n), that is the alphabet, the membrane structure, the initial configuration, and the sets of rules) is bounded by nk, for some constant k depending on A. 2. Each IIA(n) is confluent: there is a constant tA(n) and a distinguished object yes such that IIA(n) always halts
Data Loading...
