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}, }

Powered by bibtexbrowser