共查询到20条相似文献,搜索用时 15 毫秒
1.
Antonio E. Porreca Alberto Leporati Giancarlo Mauri Claudio Zandron 《Natural computing》2011,10(1):167-182
We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to
solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved
by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules,
are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential
time and polynomial space problems that cannot be solved in polynomial time, unless P = SPACE. 相似文献
2.
The P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type, where membrane division is the frequently investigated way for obtaining an exponential working space in a linear time, and on this basis solving hard problems, typically NP-complete problems, in polynomial (often, linear) time. In this paper, using another way to obtain exponential working space – membrane separation, it was shown that Satisfiability Problem and Hamiltonian Path Problem can be deterministically solved in linear or polynomial time by a uniform family of P systems with separation rules, where separation rules are not changing labels, but polarizations are used. Some related open problems are mentioned. 相似文献
3.
P systems with active membranes are among the central ones in membrane computing, and they were shown to be both computationally universal (able to simulate Turing machines) and computationally efficient (able to solve hard problems in polynomial time). However, in all cases, these results were obtained by making use of several powerful features, such as membrane polarization, label changing, division of non-elementary membranes, priorities, or cooperative rules. This paper contributes to the research effort of introducing a class of P systems with active membranes having none of the features mentioned above, but still preserving the power and the efficiency. The additional feature we consider instead are the operations of endocytosis and exocytosis: moving a membrane inside a neighboring membrane, or outside the membrane where it is placed. We investigate the power and the efficiency of these systems (also using membrane division) by first proving that they can simulate (with a linear slowdown and without introducing non-determinism) rewriting P systems with 2-replication, for which the universality and the possibility of solving NP-complete problems in polynomial time are known. In this way, the universality and efficiency are also obtained for our systems. We also give a direct and simple proof for the universality result – without using division rules (the proof uses nine membranes, but we do not know whether this number can be decreased). 相似文献
4.
Gabriel Ciobanu Linqiang Pan Gheorghe Păun Mario J. Pérez-Jiménez 《Theoretical computer science》2007
A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time). 相似文献
5.
José M. Cecilia José M. García Ginés D. Guerrero Manuel Ujaldón 《The Journal of supercomputing》2014,69(1):248-272
Membrane computing is an emergent research area studying the behavior of living cells to define bio-inspired computing devices, also called P systems. Such devices provide polynomial time solutions to NP-complete problems by trading time for space. The efficient simulation of P systems poses three major challenging issues: an intrinsic massive parallelism of P systems, an exponential computational workspace, and a non-intensive floating point nature. This paper analyzes the simulation of a family of recognizer P systems with active membranes that solves the satisfiability problem in linear time on three different architectures: a shared memory multiprocessor, a distributed memory system, and a manycore graphics processing unit (GPU). For an efficient handling of the exponential workspace created by the P systems computation, we enable different data policies on those architectures to increase memory bandwidth and exploit data locality through tiling. Parallelism inherent to the target P system is also managed on each architecture to demonstrate that GPUs offer a valid alternative for high-performance computing at a considerably lower cost. Our results lead to execution time improvements exceeding 310 \(\times \) and 78 \(\times \) , respectively, for a much cheaper high-performance alternative. 相似文献
6.
We introduce a variant of P systems called maximum cooperative P systems; it consists of transition P systems with cooperative rules that evolve at each step by consuming the maximum number of objects.
The problem of distributing objects to rules in order to achieve a maximum consuming evolution is studied by introducing the
resource mapping problem. The decision version of this optimization problem is proved to be NP-complete. We describe a new simulation technique for the evolution of the maximum cooperative P systems based on integer
linear programming. Finally we illustrate the evolution by an example. 相似文献
7.
The standard definition of tissue P systems includes a special alphabet whose elements are assumed to appear in the initial configuration of the system in an arbitrarily large number of copies. These objects reside in a distinguished place of the system, called the environment. Such potentially infinite supply of objects seems an unfair tool when designing efficient solutions to computationally hard problems in the framework of membrane computing, by performing a space–time trade-off. This paper deals with computational aspects of tissue P systems with cell division where there is no environment having the property mentioned above. Specifically, we prove that the polynomial complexity classes associated with tissue P systems with cell division and with or without environment are actually identical. As a consequence, we conclude that it is not necessary to have infinitely many copies of some objects in the initial configuration in order to solve NP–complete problems in an efficient way. 相似文献
8.
Jiménez Mario J. Péerez Jiménez Álvaro Romero Caparrini Fernando Sancho 《Natural computing》2003,2(3):265-285
In this paper we introduce four complexity classes for cellularcomputing systems with membranes: the first and the second ones containall decision problems solvable in polynomial time by a family ofdeterministic P systems, without and with an input membrane,respectively; the third and fourth classes contain all decision problemssolvable in polynomial time by a family of non-deterministic P systems,without and with an input membrane, respectively. We illustrate theusefulness of these classes by solving two NP–completeproblems, namely HPP and SAT, in both variants of Psystems. 相似文献
9.
We study the computational power of cell division operations in the formalframework of P systems, a mathematical model of cell-like membrane structure with regulated transport of objects (molecules) through membranes. We show that a uniformfamily of P systems with active membranes and2-division is able to solve the well-known PSPACE-complete problem QBF inlinear time. This result implies that such a family of P systems modelling celldivision is at least as powerful as so-called Second Machine Class computers. The Second Machine Class, containing most of the fundamental parallelcomputer models such as parallel RAM machines of types SIMD and MIMD, vector machinesand others, is characterized by using an exponential amount of resources(processing units) with respect to the computing time. 相似文献
10.
Alberto Leporati Claudio Ferretti Giancarlo Mauri Mario J. Pérez-Jiménez Claudio Zandron 《Natural computing》2009,8(4):703-717
We investigate polarizationless P systems with active membranes working in maximally parallel manner, which do not make use
of evolution or communication rules, in order to find which features are sufficient to efficiently solve computationally hard
problems. We show that such systems are able to solve the PSPACE-complete problem Quantified 3-sat, provided that non-elementary membrane division is controlled by the presence of a (possibly non-elementary) membrane. 相似文献
11.
Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources 总被引:1,自引:0,他引:1
We consider the possibility of using spiking neural P systems for solving computationally hard problems, under the assumption
that some (possibly exponentially large) pre-computed resources are given in advance. In particular, we propose two uniform
families of spiking neural P systems which can be used to address the NP-complete problems sat and 3-sat, respectively. Each system in the first family is able to solve all the instances of sat which can be built using n Boolean variables and m clauses, in a time which is quadratic in n and linear in m. Similarly, each system of the second family is able to solve all the instances of 3-sat that contain n Boolean variables, in a time which is cubic in n. All the systems here considered are deterministic. 相似文献
12.
Linqiang Pan Carlos Martín-Vide 《Journal of Parallel and Distributed Computing》2005,65(12):1578-1584
Membrane systems are biologically motivated theoretical models of distributed and parallel computing. In this paper, we present a membrane algorithm to solve multidimensional 0–1 knapsack problem in linear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modified to solve general 0–1 integer programming problem. 相似文献
13.
《Journal of Parallel and Distributed Computing》2006,66(6):867-872
P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type. In this paper, some restrictions on the general form of the developing rules are considered, under which it is still possible to solve NP-complete problems. We present an algorithm for deterministically deciding SAT in linear time by P systems with active membranes using two polarizations and rules of restricted versions of types (a), (c), (e). The result obtained in this paper answered an open problem proposed by Alhazov and Freund in the aspect of computing efficiency. 相似文献
14.
Artiom Alhazov 《New Generation Computing》2004,22(4):299-310
Evolution-communication P systems are a variant of P systems allowing both rewriting rules and symport/antiport rules, thus
having separated the rewriting and the communication. The purpose of this paper is to solve an open problem stated in Reference,1) namely generating the family of Turing computable sets of vectors of natural numbers instead of the family of Turing computable
sets of natural numbers. The same construction also reduces the 3-membrane non-cooperative case and the 2-membrane 1-catalyst
case to the 2-membrane non-cooperative case. Also, EC P automata are introduced and it is proved that 2-membrane EC P automata
with a promoter can accept all recursively enumerable languages. Finally, a definition of an extended system is given, and
its universality is proved using the rules of more restricted types.
Artiom Alhazov: He has graduated from Mathematics and Computer Science, State University of Moldova in 2001, and is currently a Ph.D. student
in Chişinăm, Moldova, and Tarragona, Spain. He has won prizes at 3 National Olympiads in Informatics and in Mathematics (1995
and 1996), participated at 8th International Olympiad in Informatics (Veszprem, Hungary, 1996). He has experience in programming
and teaching, and has published 18 papers, mostly in Membrane Computing. His interests are Origami, Mathematics, Programming,
Theoretical Computer Science, Formal Linguistics and Biocomputing. 相似文献
15.
In this paper we give several improved universality results for two important classes of P systems: P systems with catalysts
and evolution-communication P systems. First, the result from Reference,14) stating that six catalysts ensure the universality, has been improved in two ways: using bistable catalysts and using moving
catalysts. Specifically, the universality can be reached with one bistable catalyst and 2 usual catalysts (using five membranes),
as well as with one moving catalyst and three membranes, or with two moving catalysts and only two membranes. The second part
of the paper deals with evolution-communication P systems, and we also give improved universality results for this type of
systems, in terms of the weight of symport/antiport rules, number of membranes, or number of catalysts.
Shankara Narayanan Krishna: She is an Assistant Professor in Dept. Computer Science & Engg, IIT Bombay, India. Her research interests are Natural Computing
and Formal Methods.
Andrei Paun, Ph.D.: He obtained his bachelor degree in Mathematics and Computer Science from the University of Bucharest, Romania. He obtaind
his Ph.D. degree in Computer Science, at University of Western Ontario, Canada, under the supervision of Prof. Dr. Sheng Yu,
with the thesis “Unconventional Models of Computation: DNA and Membrane Computing”. After graduation he received a postdoctoral
felloship from NSERC, Canada and after six months he accepted an assistant professor position in US at Louisiana Tech University. 相似文献
16.
We present the first membrance computing solution to the Subset-Sum problem using a family of deterministic P systems with active membranes. We do not use priority among rules, membrane dissolution nor cooperation; it suffices to control the electrical charges of the membranes and to introduce some counters. The number of steps of any computation is of the linear order (but it is necessary a polynomial-time of precomputed resources). 相似文献
17.
We apply techniques from complexity theory to a model of biological cellular membranes known as membrane systems or P-systems.
Like Boolean circuits, membrane systems are defined as uniform families of computational devices. To date, polynomial time
uniformity has been the accepted uniformity notion for membrane systems. Here, we introduce the idea of using AC
0-uniformity and investigate the computational power of membrane systems under these tighter conditions. It turns out that
the computational power of some systems is lowered from P to NL when using AC
0-semi-uniformity, so we argue that this is a more reasonable uniformity notion for these systems as well as others. Interestingly,
other P-semi-uniform systems that are known to be lower-bounded by P are shown to retain their P lower-bound under the new tighter semi-uniformity condition. Similarly, a number of membrane systems that are known to solve
PSPACE-complete problems retain their computational power under tighter uniformity conditions. 相似文献
18.
Spiking neural P systems with neuron division and budding 总被引:1,自引:0,他引:1
Spiking neural P systems are a class of distributed and parallel computing models inspired by spiking neurons.In this work,the features of neuron division and neuron budding are introduced into the framework of spiking neural P systems,which are processes inspired by neural stem cell division. With neuron division and neuron budding,a spiking neural P system can generate exponential work space in polynomial time as the case for P systems with active membranes.In this way,spiking neural P systems can efficie... 相似文献
19.
Alberto Leporati Giancarlo Mauri Claudio Zandron Gheorghe Păun Mario J. Pérez-Jiménez 《Natural computing》2009,8(4):681-702
We continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally
hard problems, addressing two problems which were already recently considered in this respect: Subset Sum{\tt Subset}\,{\tt Sum} and SAT.{\tt SAT}. For both of them we provide uniform constructions of standard spiking neural P systems (i.e., not using extended rules or
parallel use of rules) which solve these problems in a constant number of steps, working in a non-deterministic way. This
improves known results of this type where the construction was non-uniform, and/or was using various ingredients added to
the initial definition of spiking neural P systems (the SN P systems as defined initially are called here “standard”). However,
in the Subset Sum{\tt Subset}\,{\tt Sum} case, a price to pay for this improvement is that the solution is obtained either in a time which depends on the value of
the numbers involved in the problem, or by using a system whose size depends on the same values, or again by using complicated
regular expressions. A uniform solution to 3-SAT{\tt SAT} is also provided, that works in constant time. 相似文献
20.
José M. Cecilia José M. García Ginés D. Guerrero Miguel A. Martínez-del-Amor Mario J. Pérez-Jiménez Manuel Ujaldón 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2012,16(2):231-246
Membrane Computing is a discipline aiming to abstract formal computing models, called membrane systems or P systems, from the structure and functioning of the living cells as well as from the cooperation of cells in tissues, organs, and
other higher order structures. This framework provides polynomial time solutions to NP-complete problems by trading space
for time, and whose efficient simulation poses challenges in three different aspects: an intrinsic massively parallelism of
P systems, an exponential computational workspace, and a non-intensive floating point nature. In this paper, we analyze the
simulation of a family of recognizer P systems with active membranes that solves the Satisfiability problem in linear time
on different instances of Graphics Processing Units (GPUs). For an efficient handling of the exponential workspace created
by the P systems computation, we enable different data policies to increase memory bandwidth and exploit data locality through
tiling and dynamic queues. Parallelism inherent to the target P system is also managed to demonstrate that GPUs offer a valid
alternative for high-performance computing at a considerably lower cost. Furthermore, scalability is demonstrated on the way
to the largest problem size we were able to run, and considering the new hardware generation from Nvidia, Fermi, for a total
speed-up exceeding four orders of magnitude when running our simulations on the Tesla S2050 server. 相似文献