Back to Search
Start Over
A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem
- Source :
- idUS: Depósito de Investigación de la Universidad de Sevilla, Universidad de Sevilla (US), idUS. Depósito de Investigación de la Universidad de Sevilla, instname
- Publication Year :
- 2011
- Publisher :
- IOS Press, 2011.
-
Abstract
- A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NP-complete problems. An answer to this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules Ministerio de Educación y Ciencia TIN2009-13192 Junta de Andalucía P08-TIC-04200
- Subjects :
- Algebra and Number Theory
Theoretical computer science
Cell division
Matching (graph theory)
Open problem
Membrane Computing
Topology
Theoretical Computer Science
Exponential function
Computational Theory and Mathematics
Tissue P Systems
Tripartite Matching Problem
Time complexity
Membrane computing
P system
Information Systems
Mathematics
Subjects
Details
- ISSN :
- 01692968
- Volume :
- 109
- Database :
- OpenAIRE
- Journal :
- Fundamenta Informaticae
- Accession number :
- edsair.doi.dedup.....f3cdc4cdf00e524dfb2821745df9d6fb