A Solution of Horn-SAT with P Systems Using Antimatter

摘要

In this paper we prove that uniform families of P systems with active membranes and using antimatter characterize the complexity class P when polarizations, dissolution rules and membrane division rules are not used. This means that the use of antimatter significantly increases the computational power of these systems having the above restrictions, since it is known that without the use of antimatter and using reasonably weak uniformity conditions they have very limited computational power only.