Affiliations: Research Group on Natural Computing, Dpt. Computer Science and Artificial Intelligence, University of Sevilla, 41012 Seville, Spain. marper@us.es | Research Group on Natural Computing, Dpt. Computer Science and Artificial Intelligence, University of Sevilla, 41012 Seville, Spain. ariscosn@us.es | Department of Applied Mathematics IV, Universitat Politécnica de Catalunya, Edifici C3, Despatx 016, Av. del Canal Olimpic s/n, 08860 Casteldefels, Spain. mrius@ma4.upc.edu | Research Group on Natural Computing, Dpt. Computer Science and Artificial Intelligence, University of Sevilla, 41012 Seville, Spain. fran@us.es
Note: [] Address for correspondence: Research Group on Natural Computing, Dpt. Computer Science and Artificial Intelligence, University of Sevilla, 41012 Seville, Spain
Abstract: In 1936 A. Turing showed the existence of a universal machine able to simulate any Turing machine given its description. In 1956, C. Shannon formulated for the first time the problem of finding the smallest possible universal Turing machine according to some critera to measure its size such as the number of states and symbols. Within the framework of Membrane Computing different studies have addressed this problem: small universal symport/antiport P systems (by considering the number of membranes, the weight of the rules and the number of objects as a measure of the size of the system), small universal splicing P systems (by considering the number of rules as a measure of the size of the system), and small universal spiking neural P systems (by considering the number of neurons as a measure of the size of the system). In this paper the problem of determining the smallest possible efficient P system is explicitly formulated. Efficiency within the framework of Membrane Computing refers to the capability of solving computationally hard problems (i.e. problems such that classical electronic computer cannot solve instances of medium/large size in any reasonable amount of time) in polynomial time. A descriptive measure to define precisely the notion of small P system is presented in this paper.
Keywords: Membrane Computing, Small universal P Systems, Small effcient P systems, SAT problem
