Artículo
P systems with input in binary form
Autor/es | Leporati, Alberto
Zandron, Claudio Gutiérrez Naranjo, Miguel Ángel |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2006 |
Fecha de depósito | 2024-04-23 |
Publicado en |
|
Resumen | 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 ... 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. |
Cita | Leporati, A., Zandron, C. y Gutiérrez Naranjo, M.Á. (2006). P systems with input in binary form. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 17 (1), 127-146. https://doi.org/10.1142/S0129054106003735. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
11_psystems_with_input.pdf | 129.8Kb | [PDF] | Ver/ | |