A computational complexity theory in membrane computing. (English) Zbl 1273.68185
Păun, Gheorghe (ed.) et al., Membrane computing. 10th international workshop, WMC 2009, Curtea de Arges, Romania, August 24–27, 2009. Revised selected and invited papers. Berlin: Springer (ISBN 978-3-642-11466-3/pbk). Lecture Notes in Computer Science 5957, 125-148 (2010).
Summary: In this paper, a computational complexity theory within the framework of membrane computing is introduced. Polynomial complexity classes associated with different models of cell-like and tissue-like membrane systems are defined and the most relevant results obtained so far are presented. Many attractive characterizations of \(\text{P} \neq \text{NP}\) conjecture within the framework of a bio-inspired and non-conventional computing model are deduced.
For the entire collection see [Zbl 1179.68004].
For the entire collection see [Zbl 1179.68004].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
