Memorias de investigación
Communications at congresses:
Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges
Year:2014

Research Areas
  • Information technology and adata processing

Information
Abstract
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.
International
Si
Congress
Membrane Computing. 14th International Conference, CMC 2013
960
Place
Reviewers
Si
ISBN/ISSN
978-3-642-54238-1
Start Date
20/08/2013
End Date
23/08/2013
From page
40
To page
55
Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges
Participants

Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: Grupo de Inteligencia Artificial (LIA)
  • Departamento: Inteligencia Artificial