Non-confluence in divisionless P systems with active membranes |
| |
Authors: | Antonio E Porreca Giancarlo Mauri |
| |
Affiliation: | a Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, viale Sarca 336, 20126 Milano, Italy |
| |
Abstract: | We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide an algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slowdown. Together, these results prove that the complexity class of problems solvable non-confluently and in polynomial time by this kind of P system is exactly the class . |
| |
Keywords: | Membrane computing Complexity theory |
本文献已被 ScienceDirect 等数据库收录! |
|