dc.contributor.author |
Paun, G |
en |
dc.date.accessioned |
2009-04-16T23:11:57Z |
en |
dc.date.available |
2009-04-16T23:11:57Z |
en |
dc.date.issued |
1999-05 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-102 (1999) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3611 |
en |
dc.description.abstract |
P systems are parallel Molecular Computing models based on processing multisets of objects in cell-like membrane structures. Various variants were already
shown to be computationally universal, equal in power to Turing machines. In this
paper one proposes a class of P systems whose membranes are the main active
components, in the sense that they directly mediate the evolution and the communication of objects. Moreover, the membranes can multiply themselves by division.
We prove that this variant is not only computationally universal, but also able to
solve NP complete problems in polynomial (actually, linear) time. We exemplify
this assertion with the well-known SAT problem. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.title |
P Systems with Active Membranes: Attacking NP Complete Problems |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |