Current P systems which solve NP-complete numerical problems represent instances in unary notation. 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 this does not occur when working with P systems. Namely, 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.
Gutiérrez Naranjo, M., Leporati, A., Zandron, C. (2005). Converting integer numbers from binary to unary notation with P systems. In Cellular Computing (Complexity Aspect), ESF PESC Exploratory Workshop (pp.201-208). Seville : Fénix Editora.
Converting integer numbers from binary to unary notation with P systems
LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO
2005
Abstract
Current P systems which solve NP-complete numerical problems represent instances in unary notation. 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 this does not occur when working with P systems. Namely, 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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
