From NP-Completeness to DP-Completeness: A Membrane Computing Perspective

Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ in polynomial time and in a uniform way. PMCℛ...

Full description

Saved in:
Bibliographic Details
Published in:Complexity (New York, N.Y.) N.Y.), 2020, Vol.2020 (2020), p.1-10
Main Authors: Pérez-Hurtado, Ignacio, Martínez-del-Amor, Miguel Á., Orellana-Martín, David, Valencia-Cabrera, Luis, Pérez-Jiménez, Mario J.
Format: Article
Language:English
Subjects:
Completeness
Language
Lower bounds
Membranes
Polynomials
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c465t-346c0215c7b8ac2363beb1c2e72fcd4bcbc6926b1801aecaaad30cd67c0954743
cites cdi_FETCH-LOGICAL-c465t-346c0215c7b8ac2363beb1c2e72fcd4bcbc6926b1801aecaaad30cd67c0954743
container_end_page 10
container_issue 2020
container_start_page 1
container_title Complexity (New York, N.Y.)
container_volume 2020
creator Pérez-Hurtado, Ignacio
Martínez-del-Amor, Miguel Á.
Orellana-Martín, David
Valencia-Cabrera, Luis
Pérez-Jiménez, Mario J.
description Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ in polynomial time and in a uniform way. PMCℛ is closed under complement and under polynomial-time reduction. Therefore, if ℛ is a presumably efficient computing model of recognizer membrane systems, then NP ∪ co-NP ⊆ PMCℛ. In this paper, the lower bound NP ∪ co-NP for the time complexity class PMCℛ is improved for any presumably efficient computing model ℛ of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that DP ∪ co-DP is a lower bound for such PMCℛ, where DP is the class of differences of any two languages in NP. Since NP ∪ co-NP ⊆ DP ∩ co-DP, this lower bound for PMCℛ delimits a thinner frontier than that with NP ∪ co-NP.
doi_str_mv 10.1155/2020/6765097
format article
fullrecord <record><control><sourceid>gale_doaj_</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_b4818bce4dc344518deae5cec7ef020f</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><galeid>A821702781</galeid><doaj_id>oai_doaj_org_article_b4818bce4dc344518deae5cec7ef020f</doaj_id><sourcerecordid>A821702781</sourcerecordid><originalsourceid>FETCH-LOGICAL-c465t-346c0215c7b8ac2363beb1c2e72fcd4bcbc6926b1801aecaaad30cd67c0954743</originalsourceid><addsrcrecordid>eNqFkc1P3DAQxaMKpMLSW89VpB4h4G8nva2WLiDRlkN7tuzJZOvVJl7sLKj_PV6Cijgh27L1_Junp5mi-EzJOaVSXjDCyIXSSpJGfyiOKGmaikimDvZvrSqma_2xOE5pTQhpFNdHxc0yhr78eVctQr_d4IgDplSOobx8K30r5-UP7F20A5b7j93oh1V5hzFtEUb_gCfFYWc3CT-93LPiz_L778V1dfvr6mYxv61AKDlWXCggjErQrrbAuOIOHQWGmnXQCgcOVMOUozWhFsFa23ICrdJAGim04LOc-dm3DXZtttH3Nv4zwXrzLIS4MjaOHjZonKhp7QBFC1wISesWLUpA0NjlVnXZ6-vktY3hfodpNOuwi0OOb5gQOSWv85kV5xO1stnUD10Yo4W8Wuw9hAE7n_V5zagmucU0F5xNBRBDShG7_zEpMftJmf2kzMukMn464X_90NpH_x79ZaIxM9jZV5oKzvN-AuRqm44</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2442153815</pqid></control><display><type>article</type><title>From NP-Completeness to DP-Completeness: A Membrane Computing Perspective</title><source>Wiley-Blackwell Open Access Collection</source><creator>Pérez-Hurtado, Ignacio ; Martínez-del-Amor, Miguel Á. ; Orellana-Martín, David ; Valencia-Cabrera, Luis ; Pérez-Jiménez, Mario J.</creator><contributor>Valverde, Jose C. ; Jose C Valverde</contributor><creatorcontrib>Pérez-Hurtado, Ignacio ; Martínez-del-Amor, Miguel Á. ; Orellana-Martín, David ; Valencia-Cabrera, Luis ; Pérez-Jiménez, Mario J. ; Valverde, Jose C. ; Jose C Valverde</creatorcontrib><description>Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ in polynomial time and in a uniform way. PMCℛ is closed under complement and under polynomial-time reduction. Therefore, if ℛ is a presumably efficient computing model of recognizer membrane systems, then NP ∪ co-NP ⊆ PMCℛ. In this paper, the lower bound NP ∪ co-NP for the time complexity class PMCℛ is improved for any presumably efficient computing model ℛ of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that DP ∪ co-DP is a lower bound for such PMCℛ, where DP is the class of differences of any two languages in NP. Since NP ∪ co-NP ⊆ DP ∩ co-DP, this lower bound for PMCℛ delimits a thinner frontier than that with NP ∪ co-NP.</description><identifier>ISSN: 1076-2787</identifier><identifier>EISSN: 1099-0526</identifier><identifier>DOI: 10.1155/2020/6765097</identifier><language>eng</language><publisher>Cairo, Egypt: Hindawi Publishing Corporation</publisher><subject>Completeness ; Language ; Lower bounds ; Membranes ; Polynomials</subject><ispartof>Complexity (New York, N.Y.), 2020, Vol.2020 (2020), p.1-10</ispartof><rights>Copyright © 2020 Luis Valencia-Cabrera et al.</rights><rights>COPYRIGHT 2020 John Wiley &amp; Sons, Inc.</rights><rights>Copyright © 2020 Luis Valencia-Cabrera et al. This is an open access article distributed under the Creative Commons Attribution License (the “License”), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License. http://creativecommons.org/licenses/by/4.0</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c465t-346c0215c7b8ac2363beb1c2e72fcd4bcbc6926b1801aecaaad30cd67c0954743</citedby><cites>FETCH-LOGICAL-c465t-346c0215c7b8ac2363beb1c2e72fcd4bcbc6926b1801aecaaad30cd67c0954743</cites><orcidid>0000-0002-2892-6775 ; 0000-0002-5055-0102 ; 0000-0001-9735-7951 ; 0000-0002-6576-9529 ; 0000-0003-1065-8802</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,4022,27921,27922,27923</link.rule.ids></links><search><contributor>Valverde, Jose C.</contributor><contributor>Jose C Valverde</contributor><creatorcontrib>Pérez-Hurtado, Ignacio</creatorcontrib><creatorcontrib>Martínez-del-Amor, Miguel Á.</creatorcontrib><creatorcontrib>Orellana-Martín, David</creatorcontrib><creatorcontrib>Valencia-Cabrera, Luis</creatorcontrib><creatorcontrib>Pérez-Jiménez, Mario J.</creatorcontrib><title>From NP-Completeness to DP-Completeness: A Membrane Computing Perspective</title><title>Complexity (New York, N.Y.)</title><description>Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ in polynomial time and in a uniform way. PMCℛ is closed under complement and under polynomial-time reduction. Therefore, if ℛ is a presumably efficient computing model of recognizer membrane systems, then NP ∪ co-NP ⊆ PMCℛ. In this paper, the lower bound NP ∪ co-NP for the time complexity class PMCℛ is improved for any presumably efficient computing model ℛ of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that DP ∪ co-DP is a lower bound for such PMCℛ, where DP is the class of differences of any two languages in NP. Since NP ∪ co-NP ⊆ DP ∩ co-DP, this lower bound for PMCℛ delimits a thinner frontier than that with NP ∪ co-NP.</description><subject>Completeness</subject><subject>Language</subject><subject>Lower bounds</subject><subject>Membranes</subject><subject>Polynomials</subject><issn>1076-2787</issn><issn>1099-0526</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2020</creationdate><recordtype>article</recordtype><sourceid>DOA</sourceid><recordid>eNqFkc1P3DAQxaMKpMLSW89VpB4h4G8nva2WLiDRlkN7tuzJZOvVJl7sLKj_PV6Cijgh27L1_Junp5mi-EzJOaVSXjDCyIXSSpJGfyiOKGmaikimDvZvrSqma_2xOE5pTQhpFNdHxc0yhr78eVctQr_d4IgDplSOobx8K30r5-UP7F20A5b7j93oh1V5hzFtEUb_gCfFYWc3CT-93LPiz_L778V1dfvr6mYxv61AKDlWXCggjErQrrbAuOIOHQWGmnXQCgcOVMOUozWhFsFa23ICrdJAGim04LOc-dm3DXZtttH3Nv4zwXrzLIS4MjaOHjZonKhp7QBFC1wISesWLUpA0NjlVnXZ6-vktY3hfodpNOuwi0OOb5gQOSWv85kV5xO1stnUD10Yo4W8Wuw9hAE7n_V5zagmucU0F5xNBRBDShG7_zEpMftJmf2kzMukMn464X_90NpH_x79ZaIxM9jZV5oKzvN-AuRqm44</recordid><startdate>2020</startdate><enddate>2020</enddate><creator>Pérez-Hurtado, Ignacio</creator><creator>Martínez-del-Amor, Miguel Á.</creator><creator>Orellana-Martín, David</creator><creator>Valencia-Cabrera, Luis</creator><creator>Pérez-Jiménez, Mario J.</creator><general>Hindawi Publishing Corporation</general><general>Hindawi</general><general>John Wiley &amp; Sons, Inc</general><general>Hindawi Limited</general><general>Hindawi-Wiley</general><scope>ADJCN</scope><scope>AHFXO</scope><scope>AHMDM</scope><scope>RHU</scope><scope>RHW</scope><scope>RHX</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7XB</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8G5</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>M2O</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>Q9U</scope><scope>DOA</scope><orcidid>https://orcid.org/0000-0002-2892-6775</orcidid><orcidid>https://orcid.org/0000-0002-5055-0102</orcidid><orcidid>https://orcid.org/0000-0001-9735-7951</orcidid><orcidid>https://orcid.org/0000-0002-6576-9529</orcidid><orcidid>https://orcid.org/0000-0003-1065-8802</orcidid></search><sort><creationdate>2020</creationdate><title>From NP-Completeness to DP-Completeness: A Membrane Computing Perspective</title><author>Pérez-Hurtado, Ignacio ; Martínez-del-Amor, Miguel Á. ; Orellana-Martín, David ; Valencia-Cabrera, Luis ; Pérez-Jiménez, Mario J.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c465t-346c0215c7b8ac2363beb1c2e72fcd4bcbc6926b1801aecaaad30cd67c0954743</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2020</creationdate><topic>Completeness</topic><topic>Language</topic><topic>Lower bounds</topic><topic>Membranes</topic><topic>Polynomials</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Pérez-Hurtado, Ignacio</creatorcontrib><creatorcontrib>Martínez-del-Amor, Miguel Á.</creatorcontrib><creatorcontrib>Orellana-Martín, David</creatorcontrib><creatorcontrib>Valencia-Cabrera, Luis</creatorcontrib><creatorcontrib>Pérez-Jiménez, Mario J.</creatorcontrib><collection>الدوريات العلمية والإحصائية - e-Marefa Academic and Statistical Periodicals</collection><collection>معرفة - المحتوى العربي الأكاديمي المتكامل - e-Marefa Academic Complete</collection><collection>قاعدة العلوم الإنسانية - e-Marefa Humanities</collection><collection>Hindawi Publishing Complete</collection><collection>Hindawi Publishing Subscription Journals</collection><collection>Hindawi Publishing Open Access Journals</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>Research Library (Alumni Edition)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>ProQuest research library</collection><collection>Research Library (Corporate)</collection><collection>ProQuest advanced technologies &amp; aerospace journals</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>ProQuest Central Basic</collection><collection>DOAJ Directory of Open Access Journals</collection><jtitle>Complexity (New York, N.Y.)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Pérez-Hurtado, Ignacio</au><au>Martínez-del-Amor, Miguel Á.</au><au>Orellana-Martín, David</au><au>Valencia-Cabrera, Luis</au><au>Pérez-Jiménez, Mario J.</au><au>Valverde, Jose C.</au><au>Jose C Valverde</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>From NP-Completeness to DP-Completeness: A Membrane Computing Perspective</atitle><jtitle>Complexity (New York, N.Y.)</jtitle><date>2020</date><risdate>2020</risdate><volume>2020</volume><issue>2020</issue><spage>1</spage><epage>10</epage><pages>1-10</pages><issn>1076-2787</issn><eissn>1099-0526</eissn><abstract>Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ in polynomial time and in a uniform way. PMCℛ is closed under complement and under polynomial-time reduction. Therefore, if ℛ is a presumably efficient computing model of recognizer membrane systems, then NP ∪ co-NP ⊆ PMCℛ. In this paper, the lower bound NP ∪ co-NP for the time complexity class PMCℛ is improved for any presumably efficient computing model ℛ of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that DP ∪ co-DP is a lower bound for such PMCℛ, where DP is the class of differences of any two languages in NP. Since NP ∪ co-NP ⊆ DP ∩ co-DP, this lower bound for PMCℛ delimits a thinner frontier than that with NP ∪ co-NP.</abstract><cop>Cairo, Egypt</cop><pub>Hindawi Publishing Corporation</pub><doi>10.1155/2020/6765097</doi><tpages>10</tpages><orcidid>https://orcid.org/0000-0002-2892-6775</orcidid><orcidid>https://orcid.org/0000-0002-5055-0102</orcidid><orcidid>https://orcid.org/0000-0001-9735-7951</orcidid><orcidid>https://orcid.org/0000-0002-6576-9529</orcidid><orcidid>https://orcid.org/0000-0003-1065-8802</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1076-2787
ispartof Complexity (New York, N.Y.), 2020, Vol.2020 (2020), p.1-10
issn 1076-2787
1099-0526
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_b4818bce4dc344518deae5cec7ef020f
source Wiley-Blackwell Open Access Collection
subjects Completeness
Language
Lower bounds
Membranes
Polynomials
title From NP-Completeness to DP-Completeness: A Membrane Computing Perspective
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-09T11%3A57%3A57IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-gale_doaj_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=From%20NP-Completeness%20to%20DP-Completeness:%20A%20Membrane%20Computing%20Perspective&rft.jtitle=Complexity%20(New%20York,%20N.Y.)&rft.au=P%C3%A9rez-Hurtado,%20Ignacio&rft.date=2020&rft.volume=2020&rft.issue=2020&rft.spage=1&rft.epage=10&rft.pages=1-10&rft.issn=1076-2787&rft.eissn=1099-0526&rft_id=info:doi/10.1155/2020/6765097&rft_dat=%3Cgale_doaj_%3EA821702781%3C/gale_doaj_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c465t-346c0215c7b8ac2363beb1c2e72fcd4bcbc6926b1801aecaaad30cd67c0954743%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2442153815&rft_id=info:pmid/&rft_galeid=A821702781&rfr_iscdi=true