|
Descripción
|
|
|---|---|
| We resume computational complexity aspects of several models of membrane systems, namely P systems with active membranes, P systems with proteins on membranes and tissue P systems both with membrane separation and membrane division. A sequence of common issues is studied in relation to these P system models, and 16 open problems are stated in the text.We question the role of families of P systems and their necessity to solve computationally hard problems in polynomial time. For each P system model we focus on conditions guaranteeing the polynomial equivalence of families of P systems and Turing machines. The ability of P systems to solve NP/co-NP-complete problems in polynomial time (trading space for time) is a very popular issue. Interesting characterizations of the borderline between tractability and intractability, i.e., P/ NP, have been recently shown. Similarly important, although less popular, is the relation between NP/ co-NP and further classes as PP, the polynomial hierarchy PH and PSPACE. Several models of P systems has been shown to characterize the class PSPACE which itself characterizes parallel computations with an unlimited number of processors but a limited propagation of data between them. | |
|
Internacional
|
Si |
|
Nombre congreso
|
Membrane Computing. 14th International Conference, CMC 2013 |
|
Tipo de participación
|
960 |
|
Lugar del congreso
|
|
|
Revisores
|
Si |
|
ISBN o ISSN
|
978-3-642-54238-1 |
|
DOI
|
|
|
Fecha inicio congreso
|
20/08/2013 |
|
Fecha fin congreso
|
23/08/2013 |
|
Desde la página
|
40 |
|
Hasta la página
|
55 |
|
Título de las actas
|
Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges |