|
Descripción
|
|
|---|---|
| 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. | |
|
Internacional
|
Si |
|
JCR del ISI
|
No |
|
Título de la revista
|
Lecture notes in computer science |
|
ISSN
|
0302-9743 |
|
Factor de impacto JCR
|
0 |
|
Información de impacto
|
|
|
Volumen
|
5957 |
|
DOI
|
http://dx.doi.org/10.1007/978-3-642-11467-0_30 |
|
Número de revista
|
0 |
|
Desde la página
|
448 |
|
Hasta la página
|
460 |
|
Mes
|
ENERO |
|
Ranking
|
|