The P versus NP Problem from the Membrane Computing View

Mario J. Pérez-Jiménez

European Review, 2014, vol. 22, issue 1, 18-33

Abstract: In the last few decades several computing models using powerful tools from Nature have been developed (because of this, they are known as bio-inspired models). Commonly, the space-time trade-off method is used to develop efficient solutions to computationally hard problems. According to this, implementation of such models (in biological, electronic, or any other substrate) would provide a significant advance in the practical resolution of hard problems. Membrane Computing is a young branch of Natural Computing initiated by Gh. Păun at the end of 1998. It is inspired by the structure and functioning of living cells, as well as from the organization of cells in tissues, organs, and other higher order structures. The devices of this paradigm, called P systems or membrane systems, constitute models for distributed, parallel and non-deterministic computing. 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. Different borderlines between efficiency and non-efficiency are shown, and many attractive characterizations of the P ≠ NP conjecture within the framework of this bio-inspired and non-conventional computing model are studied.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.cambridge.org/core/product/identifier/ ... type/journal_article link to article abstract page (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cup:eurrev:v:22:y:2014:i:01:p:18-33_00

Access Statistics for this article

More articles in European Review from Cambridge University Press Cambridge University Press, UPH, Shaftesbury Road, Cambridge CB2 8BS UK.
Bibliographic data for series maintained by Kirk Stebbing ().