Solving HPP and SAT by P Systems with Active Membranes and Separation Rules (bibtex)
by Linqiang, Pan and Alhazov, Artiom
Abstract:
The P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type, where membrane division is the frequently investigated way for obtaining an exponential working space in a linear time, and on this basis solving hard problems, typically NP-complete problems, in polynomial (often, linear) time. In this paper, using another way to obtain exponential working space - membrane separation, it was shown that Satisfiability Problem and Hamiltonian Path Problem can be deterministically solved in linear or polynomial time by a uniform family of P systems with separation rules, where separation rules are not changing labels, but polarizations are used. Some related open problems are mentioned.
Reference:
Solving HPP and SAT by P Systems with Active Membranes and Separation Rules (Linqiang, Pan and Alhazov, Artiom), In Acta Informatica, Springer-Verlag, volume 43, 2006.
Bibtex Entry:
@Article{j88,
author    = {Linqiang, Pan AND Alhazov, Artiom},
title     = {Solving HPP and SAT by P Systems with Active Membranes and Separation Rules},
journal   = {Acta Informatica},
year      = {2006},
volume    = {43},
number    = {2},
pages     = {131-145},
abstract  = {The P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type, where membrane division is the frequently investigated way for obtaining an exponential working space in a linear time, and on this basis solving hard problems, typically NP-complete problems, in polynomial (often, linear) time. In this paper, using another way to obtain exponential working space - membrane separation, it was shown that Satisfiability Problem and Hamiltonian Path Problem can be deterministically solved in linear or polynomial time by a uniform family of P systems with separation rules, where separation rules are not changing labels, but polarizations are used. Some related open problems are mentioned.},
file      = {PA2006a.pdf:pdfs/PA2006a.pdf:PDF},
keywords  = {NP-complete problems, P systems, active membranes, membrane separation},
publisher = {Springer-Verlag},
}