ROMANIAN JOURNAL OF INFORMATION SCIENCE AND
TECHNOLOGY Volume 4, Numbers 1-2, 2001, 195 - 201
Deterministic P-systems for
Solving SAT-problem
Adam OBTULOWICZ
Institute of Mathematics, Polish Academy of Sciences, Warsaw, Poland
Abstract.
There are
presented certain deterministic P-systems for solving SAT-problem in linear
time. The P-systems and the processes generated by them have been introduced in the
papers by Gheorghe P?n (P-Systems with Active Membranes: Attacking NP Complete
Problems, Journal of Automata, Languages and Combinatorics, 6, pp. 75-90, 2000
and Computing with membranes, Journal of Computer and System Science, 61,
108-143, 2000).