P systems with input in binary form

TitleP systems with input in binary form
Publication TypeJournal Papers
Year of Publication2006
AuthorsLeporati, A., Zandron C., & Gutiérrez-Naranjo M. A.
Journal TitleInternational Journal of Foundations of Computer Science
PublisherWorld Scientific
Place PublishedLondon, U.K.
Volume17
Pages127 - 146
Abstract

Current P systems which solve NP–complete numerical problems represent the instances of the problems in unary notation. However, in classical complexity theory, based upon Turing machines, switching from binary to unary encoded instances generally corresponds to simplify the problem. In this paper we show that, when working with P systems, we can assume without loss of generality that instances are expressed in binary notation. More precisely, we propose a simple method to encode binary numbers using multisets, and a family of P systems which transforms such multisets into the usual unary notation. Such a family could thus be composed with the unary P systems currently proposed in the literature to obtain (uniform) families of P systems which solve NP–complete numerical problems with instances encoded in binary notation.

We introduce also a framework which can be used to design uniform families of P systems which solve NP–complete problems (both numerical and non-numerical) working directly on binary encoded instances, i.e., without first transforming them to unary notation. We illustrate our framework by designing a family of P systems which solves the 3-SAT problem. Next, we discuss the modifications needed to obtain a family of P systems which solves the PARTITION numerical problem.

Keywords3-SAT, 68Q10 (AMSC), 68Q17 (AMSC), Membrane computing, P systems; PARTITION
Issue1
ISSN Number0129-0541
DOI10.1142/S0129054106003735