Attacking the Common Algorithmic Problem by recognizer P systems

TitleAttacking the Common Algorithmic Problem by recognizer P systems
Publication TypeJournal Papers
Year of Publication2005
AuthorsPérez-Jiménez, M. J., & Romero-Campero F. J.
Journal TitleLecture Notes in Computer Science
ISBN Number978-3-540-25261-0
Place PublishedAmsterdam, The Netherlands

Many NP-complete problems can be viewed as special cases of the Common Algorithmic Problem (CAP). In a precise sense, which will be defined in the paper, one may say that CAP has a property of local universality. In this paper we present an effective solution to the decision version of the CAP using a family of recognizer P systems with active membranes. The analysis of the solution presented here will be done from the point of view of complexity classes in P systems.

ISSN Number0302-9743