Solving SAT by Symport/Antiport P Systems with Membrane Division (bibtex)
by Alhazov, Artiom
Abstract:
We present an O(n) + O(log m)-time solution of SAT with n variables and m clauses by a uniform family of deterministic P systems with communication rules (antiport-2/1 and antiport-1/2) and membrane division rules (without polarization) and unstructured environment. Nothing is sent to the environment except yes or no, in one copy. We can even start with the empty environment if we also use symport-1 rules.
Reference:
Solving SAT by Symport/Antiport P Systems with Membrane Division (Alhazov, Artiom), In Cellular Computing (Complexity Aspects), ESF PESC Exploratory Workshop (M.A. Gutierrez-Naranjo, Gh. Paun, M.J. Perez-Jimenez, ed.), Fenix Editora, Sevilla, 2005.
Bibtex Entry:
@InProceedings{inp121,
  author    = {Alhazov, Artiom},
  title     = {Solving SAT by Symport/Antiport P Systems with Membrane Division},
  booktitle = {Cellular Computing (Complexity Aspects), ESF PESC Exploratory Workshop},
  year      = {2005},
  editor    = {M.A. Gutierrez-Naranjo, Gh. Paun, M.J. Perez-Jimenez},
  pages     = {1-6},
  publisher = {Fenix Editora, Sevilla},
  abstract  = {We present an O(n) + O(log m)-time solution of SAT with n variables and m clauses by a uniform family of deterministic P systems with communication rules (antiport-2/1 and antiport-1/2) and membrane division rules (without polarization) and unstructured environment. Nothing is sent to the environment except yes or no, in one copy. We can even start with the empty environment if we also use symport-1 rules.},
  keywords  = {Satisfiability problem, Uniform solution, P system, Antiport, Membrane division, Determinism},
  pdf       = {pdfs/A2005a.pdf},
}
Powered by bibtexbrowser