Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
![]() |
![]() ![]() |
![]() PAN, Linqiang, ALHAZOV, Artiom. Solving HPP and SAT by P systems with active membranes and separation rules. In: Acta Informatica, 2006, vol. 43, pp. 131-145. ISSN 0001-5903. DOI: https://doi.org/10.1007/s00236-006-0018-8 |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Acta Informatica | ||||||
Volumul 43 / 2006 / ISSN 0001-5903 /ISSNe 1432-0525 | ||||||
|
||||||
DOI:https://doi.org/10.1007/s00236-006-0018-8 | ||||||
Pag. 131-145 | ||||||
|
||||||
![]() |
||||||
Rezumat | ||||||
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. |
||||||
Cuvinte-cheie Distributed parallel computing, Hamiltonian path problems, Hard problems, Membrane separation, Membrane system, P systems with active membranes, Polynomial-time, Satisfiability problems |
||||||
|