article · 2009

in divisionless P systems with active membranes

Antonio E. Porreca, Giancarlo Mauri, Claudio Zandron

Cited by 0Abstract and details only

Abstract

We describe a solution to the SAT problem via non-conuent 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-conuently and in polynomial time by this kind of P systems is exactly the class NP.

Cite this paper

APA 7

Porreca, A. E., Mauri, G., & Zandron, C. (2009). in divisionless P systems with active membranes.

MLA 9

Porreca, Antonio E., et al. “in divisionless P systems with active membranes.” 2009.

Chicago

Porreca, Antonio E., Giancarlo Mauri, and Claudio Zandron. 2009. “in divisionless P systems with active membranes.”

Harvard

Porreca, A.E., Mauri, G. and Zandron, C. (2009) ‘in divisionless P systems with active membranes’.

BibTeX

@article{porreca2009divisionless,
  title = {{in divisionless P systems with active membranes}},
  author = {Porreca, Antonio E. and Mauri, Giancarlo and Zandron, Claudio},
  year = {2009}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.