Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
A Lower Bound Using Mobile Membranes
verfasst von : Shankara Narayanan Krishna, Gabriel Ciobanu
Erschienen in: Descriptional Complexity of Formal Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
One of the interesting applications of membrane computing is the ability to solve intractable problems in polynomial time. The existing variants with active membranes have several powerful features like polarizations, dissolution, evolution and communication rules as well as non-elementary membrane division. We propose a simple variant which uses elementary membrane division and communication only in the form of mobility of membranes. We show that this variant has
$\Sigma_2^P \cup \Pi_2^P$
as lower bound. This is the first known treatment of the complexity classes
$\Sigma_2^P$
,
$\Pi_2^P$
using active membranes without the features of polarizations, non elementary membrane division.