Solving Subset Sum in Linear Time by Using Tissue P Systems with Cell Division
| Title | Solving Subset Sum in Linear Time by Using Tissue P Systems with Cell Division |
| Publication Type | Journal Papers |
| Year of Publication | 2007 |
| Authors | Díaz-Pernil, D., Gutiérrez-Naranjo M. A., Pérez-Jiménez M. J., & Riscos-Núñez A. |
| Journal Title | Lecture Notes in Computer Science |
| Publisher | Springer |
| Place Published | Amsterdam, The Netherlands |
| Volume | 4527 |
| Pages | 170-179 |
| Abstract | Tissue P systems with cell division is a computing model in the framework of Membrane Computing based on intercellular communication and cooperation between neurons. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to NP-complete problems in polynomial time. In this paper we present a solution to the Subset Sum problem via a family of such devices. This is the first solution to a numerical NP-complete problem by using tissue P systems with cell division. |
| URL | http://www.springerlink.com/index/q64n502j641026nu.pdf |
| ISSN Number | 0302-9743 |
| DOI | 10.1007/978-3-540-73053-8 |
Research Group on Natural Computing (PAI - TIC 193)
Department of Computer Science and Artificial Intelligence
University of Seville
Webmasters: the members of the RGNC
| Follow us: |  |
 |
|
Featured News: |
|
Mario J. Pérez-Jiménez in the top 2% of scientists of the World |
|
Agustín became Full Professor |
|
Science names our most recent research project |