Name
Abstract | ||
|---|---|---|
P systems with proteins on membranes are inspired closely by switching protein channels. This model of membrane computing using membrane division has been previously shown to solve an NP-complete problem in polynomial time. In this paper we characterize the class of problems solvable by these P systems in polynomial time and we show that it equals PSPACE. Therefore, these P systems are computationally equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer. The proof technique we employ reveals also some interesting trade-offs between certain P system properties, as antiport rules, membrane labeling by polarization or the presence of proteins. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-11467-0_30 | Workshop on Membrane Computing |
Keywords | Field | DocType |
pram computer,turing machine,membrane division,membrane computing,polynomial time reduction,polynomial time,np-complete problem,certain p system property,p system,antiport rule,np complete problem | 2-EXPTIME,Discrete mathematics,P,PSPACE,UP,Membrane computing,Mathematics,PP,P system,NP | Conference |
Volume | ISSN | ISBN |
5957 | 0302-9743 | 3-642-11466-0 |
Citations | PageRank | References |
2 | 0.37 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Petr Sosík | 1 | 479 | 68.66 |
| Andrei Paun | 2 | 743 | 74.92 |
| Alfonso Rodríguez-Patón | 3 | 435 | 51.44 |
| David Pérez | 4 | 65 | 6.71 |