Tissue P systems with cell separation: attacking the partition problem

Xingyi Zhang, Shuo Wang, Yunyun Niu, Linqiang Pan

Abstract

Tissue P systems are distributed parallel and non-deterministic computing models in the framework of membrane computing, which are inspired by intercellular communication and cooperation between neurons. Recently, cell separation is introduced into tissue P systems, which enables systems to generate an exponential workspace in a polynomial time. In this work, the computational power of tissue P systems with cell separation is investigated. Specifically, a uniform family of tissue P systems with cell separation is constructed for efficiently solving a well-known NP-complete problem, the partition problem.
BibTeX
@article{zhang2011tissue,
  author = {Xingyi Zhang and Shuo Wang and Yunyun Niu and Linqiang Pan},
  title = {{Tissue P systems with cell separation: attacking the partition problem}},
  journal = {Science China Information Sciences},
  year = {2011},
  doi = {10.1007/s11432-010-4162-y},
}

Loading related content...

Figure