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.
Membrane computing, P systems, converting numbers from binary to unary notation
English
Cellular Computing (Complexity Aspect), ESF PESC Exploratory Workshop
2005
Cellular Computing (Complexity Aspect), ESF PESC Exploratory Workshop
84-609-5338-6
2005
201
208
none
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/13145
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact