Design Patterns for Efficient Solutions to NP-Complete Problems in Membrane Computing

Many variants of P systems have the ability to generate an exponential number of membranes in linear time. This feature has been exploited to elaborate (theoretical) efficient solutions to \(\mathbf{NP}\)-complete, or even harder, problems. A thorough review of the existent solutions shows the utilization of common techniques and procedures. The abstraction of the latter into design patterns can serve to ease and accelerate the construction of efficient solutions to new hard problems.