{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:50:46Z","timestamp":1758271846761,"version":"3.37.3"},"reference-count":14,"publisher":"Wiley","license":[{"start":{"date-parts":[[2020,8,30]],"date-time":"2020-08-30T00:00:00Z","timestamp":1598745600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003329","name":"Ministerio de Econom\u00eda y Competitividad","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008530","name":"European Regional Development Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100008530","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2020,8,30]]},"abstract":"<jats:p><jats:italic>Presumably efficient<\/jats:italic> computing models are characterized by their capability to provide polynomial-time solutions for <jats:bold>NP<\/jats:bold>-complete problems. Given a class <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M1\"><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:math> of recognizer membrane systems, <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M2\"><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:math> denotes the set of decision problems solvable by families from <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M3\"><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:math> in polynomial time and in a uniform way. <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M4\"><mml:mi mathvariant=\"bold\">P<\/mml:mi><mml:mi mathvariant=\"bold\">M<\/mml:mi><mml:msub><mml:mrow><mml:mi mathvariant=\"bold\">C<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math> is closed under complement and under polynomial-time reduction. Therefore, if <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M5\"><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:math> is a presumably efficient computing model of recognizer membrane systems, then <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M6\"><mml:mi mathvariant=\"bold\">N<\/mml:mi><mml:mi mathvariant=\"bold\">P<\/mml:mi><\/mml:math>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M7\"><mml:mo>\u222a<\/mml:mo><\/mml:math>\u2009<jats:bold>co<\/jats:bold>-<jats:bold>NP<\/jats:bold>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M8\"><mml:mo>\u2286<\/mml:mo><\/mml:math>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M9\"><mml:mi mathvariant=\"bold\">P<\/mml:mi><mml:mi mathvariant=\"bold\">M<\/mml:mi><mml:msub><mml:mrow><mml:mi mathvariant=\"bold\">C<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math>. In this paper, the lower bound <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M10\"><mml:mi mathvariant=\"bold\">N<\/mml:mi><mml:mi mathvariant=\"bold\">P<\/mml:mi><\/mml:math>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M11\"><mml:mo>\u222a<\/mml:mo><\/mml:math>\u2009<jats:bold>co<\/jats:bold>-<jats:bold>NP<\/jats:bold> for the time complexity class <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M12\"><mml:mi mathvariant=\"bold\">P<\/mml:mi><mml:mi mathvariant=\"bold\">M<\/mml:mi><mml:msub><mml:mrow><mml:mi mathvariant=\"bold\">C<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math> is improved for any presumably efficient computing model <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M13\"><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:math> of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M14\"><mml:mi mathvariant=\"bold\">D<\/mml:mi><mml:mi mathvariant=\"bold\">P<\/mml:mi><\/mml:math>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M15\"><mml:mo>\u222a<\/mml:mo><\/mml:math>\u2009<jats:bold>co<\/jats:bold>-<jats:bold>DP<\/jats:bold> is a lower bound for such <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M16\"><mml:mi mathvariant=\"bold\">P<\/mml:mi><mml:mi mathvariant=\"bold\">M<\/mml:mi><mml:msub><mml:mrow><mml:mi mathvariant=\"bold\">C<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math>, where <jats:bold>DP<\/jats:bold> is the class of differences of any two languages in <jats:bold>NP<\/jats:bold>. Since <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M17\"><mml:mi mathvariant=\"bold\">N<\/mml:mi><mml:mi mathvariant=\"bold\">P<\/mml:mi><\/mml:math>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M18\"><mml:mo>\u222a<\/mml:mo><\/mml:math>\u2009<jats:bold>co<\/jats:bold>-<jats:bold>NP<\/jats:bold>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M19\"><mml:mo>\u2286<\/mml:mo><\/mml:math>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M20\"><mml:mi mathvariant=\"bold\">D<\/mml:mi><mml:mi mathvariant=\"bold\">P<\/mml:mi><\/mml:math>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M21\"><mml:mo>\u2229<\/mml:mo><\/mml:math>\u2009<jats:bold>co<\/jats:bold>-<jats:bold>DP<\/jats:bold>, this lower bound for <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M22\"><mml:mi mathvariant=\"bold\">P<\/mml:mi><mml:mi mathvariant=\"bold\">M<\/mml:mi><mml:msub><mml:mrow><mml:mi mathvariant=\"bold\">C<\/mml:mi><\/mml:mrow><mml:mrow><mml:mi mathvariant=\"normal\">\u211b<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math> delimits a thinner frontier than that with <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M23\"><mml:mi mathvariant=\"bold\">N<\/mml:mi><mml:mi mathvariant=\"bold\">P<\/mml:mi><\/mml:math>\u2009<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" id=\"M24\"><mml:mo>\u222a<\/mml:mo><\/mml:math>\u2009<jats:bold>co<\/jats:bold>-<jats:bold>NP<\/jats:bold>.<\/jats:p>","DOI":"10.1155\/2020\/6765097","type":"journal-article","created":{"date-parts":[[2020,8,30]],"date-time":"2020-08-30T23:31:23Z","timestamp":1598830283000},"page":"1-10","source":"Crossref","is-referenced-by-count":4,"title":["From NP-Completeness to DP-Completeness: A Membrane Computing Perspective"],"prefix":"10.1155","volume":"2020","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6576-9529","authenticated-orcid":true,"given":"Luis","family":"Valencia-Cabrera","sequence":"first","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012 Sevilla, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2892-6775","authenticated-orcid":true,"given":"David","family":"Orellana-Mart\u00edn","sequence":"additional","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012 Sevilla, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1065-8802","authenticated-orcid":true,"given":"Miguel \u00c1.","family":"Mart\u00ednez-del-Amor","sequence":"additional","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012 Sevilla, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9735-7951","authenticated-orcid":true,"given":"Ignacio","family":"P\u00e9rez-Hurtado","sequence":"additional","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012 Sevilla, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5055-0102","authenticated-orcid":true,"given":"Mario J.","family":"P\u00e9rez-Jim\u00e9nez","sequence":"additional","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012 Sevilla, Spain"}]}],"member":"311","reference":[{"key":"1","first-page":"388","volume-title":"Decision P systems and the P\u2260NP conjecture","volume":"2597","year":"2003"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1023\/a:1025449224520"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.06.025"},{"first-page":"94","volume-title":"Attacking NP-complete problems","year":"2000","key":"4"},{"key":"5","first-page":"224","volume-title":"On the power of dissolution in P systems with active membranes","volume":"3850","year":"2006"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.10.001"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.3233\/fi-2020-1884"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104542"},{"year":"1979","key":"9"},{"year":"1994","key":"10"},{"issue":"1","key":"11","first-page":"1","volume":"3","year":"1977","journal-title":"Theoretical Computer Science"},{"year":"1967","key":"12"},{"key":"13","first-page":"485","volume-title":"On the Boolean closure of NP","volume":"199","year":"1985"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1137\/0217078"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/6765097.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/6765097.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2020\/6765097.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,30]],"date-time":"2020-08-30T23:31:26Z","timestamp":1598830286000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.hindawi.com\/journals\/complexity\/2020\/6765097\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,30]]},"references-count":14,"alternative-id":["6765097","6765097"],"URL":"https:\/\/doi.org\/10.1155\/2020\/6765097","relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"type":"print","value":"1076-2787"},{"type":"electronic","value":"1099-0526"}],"subject":[],"published":{"date-parts":[[2020,8,30]]}}}