A fast solution to the partition problem by using tissue-like P systems

Author

Díaz-Pernil, Daniel ; Gutiérrez-Naranjo, Miguel A. ; Pérez-Jiménez, Mario J. ; Riscos-Nunez, Agustín

Author_Institution

Dept. Comput. Sci. & Artificial Intell., Univ. of Sevilla, Sevilla

fYear

2008

fDate

Sept. 28 2008-Oct. 1 2008

Firstpage

43

Lastpage

48

Abstract

Tissue-like P systems with cell division is a computing model in the framework of membrane computing based on the intercellular communication and cooperation between neurons. In such a model, the structure of the devices is a network of elementary cells. Tissue-like P systems with cell division have the ability of increasing the number of cells during the computation. In this paper we exploit this ability and present a polynomial-time solution to the (NP-complete) partition problem via a uniform family of such P systems.

Keywords

biocomputing; computational complexity; NP-complete partition problem; cell division; intercellular communication; membrane computing; neuron cooperation; polynomial-time solution; tissue-like P systems; Artificial intelligence; Biomembranes; Computer science; Concurrent computing; NP-complete problem; Neurons; Polynomials; Signal processing; Terminology; Tree graphs;

fLanguage

English

Publisher

ieee

Conference_Titel

Bio-Inspired Computing: Theories and Applications, 2008. BICTA 2008. 3rd International Conference on

Conference_Location

Adelaide, SA

Print_ISBN

978-1-4244-2724-6

Type

conf

DOI

10.1109/BICTA.2008.4656702

Filename

4656702