{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T08:55:56Z","timestamp":1783414556133,"version":"3.54.6"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2006,2]]},"abstract":"<jats:p>Current P systems which solve NP\u2013complete 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\u2013complete numerical problems with instances encoded in binary notation.<\/jats:p><jats:p>We introduce also a framework which can be used to design uniform families of P systems which solve NP\u2013complete 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.<\/jats:p>","DOI":"10.1142\/s0129054106003735","type":"journal-article","created":{"date-parts":[[2006,2,9]],"date-time":"2006-02-09T10:25:16Z","timestamp":1139480716000},"page":"127-146","source":"Crossref","is-referenced-by-count":28,"title":["P SYSTEMS WITH INPUT IN BINARY FORM"],"prefix":"10.1142","volume":"17","author":[{"given":"ALBERTO","family":"LEPORATI","sequence":"first","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u0103 degli Studi di Milano \u2013 Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"CLAUDIO","family":"ZANDRON","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Sistemistica e Comunicazione, Universit\u0103 degli Studi di Milano \u2013 Bicocca, Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MIGUEL A.","family":"GUTI\u00c9RREZ-NARANJO","sequence":"additional","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Sevilla University, Avda Reina Mercedes s\/n, 41012 Sevilla, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties","author":"Ausiello G.","year":"1999"},{"key":"rf4","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1990"},{"key":"rf5","volume-title":"Computers and Intractability. A Guide to the Theory on NP\u2013Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf12","first-page":"242","volume":"268","author":"Lipton R.","journal-title":"Science"},{"key":"rf16","first-page":"139","volume":"67","author":"P\u0103un Gh.","journal-title":"Bulletin of the EATCS"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000090"},{"key":"rf18","first-page":"75","volume":"6","author":"P\u0103un Gh.","journal-title":"J. Automata Languages and Combinatorics"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56196-2"},{"key":"rf20","first-page":"72","volume":"18","author":"P\u0103un Gh.","journal-title":"Theoria"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00136-6"},{"key":"rf23","volume":"22","author":"P\u00e9rez-Jim\u00e9nez M. J.","journal-title":"New Generation Computing"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"rf32","series-title":"DIMACS Series 54","volume-title":"DNA Based Computers V","author":"Winfree E.","year":"2001"},{"key":"rf34","doi-asserted-by":"crossref","unstructured":"C.\u00a0Zandron, C.\u00a0Ferretti and G.\u00a0Mauri, Unconventional Models of Computation, eds. I.\u00a0Antoniou, C. S.\u00a0Calude and M. J.\u00a0Dinneen (Springer\u2013Verlag, London, 2000)\u00a0pp. 289\u2013301.","DOI":"10.1007\/978-1-4471-0313-4_21"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054106003735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T12:34:14Z","timestamp":1683376454000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054106003735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,2]]},"references-count":15,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,2]]}},"alternative-id":["10.1142\/S0129054106003735"],"URL":"https:\/\/doi.org\/10.1142\/s0129054106003735","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,2]]}}}