{"entities":{"Q2205967":{"pageid":2216710,"ns":120,"title":"Item:Q2205967","lastrevid":78420140,"modified":"2026-05-06T11:33:05Z","type":"item","id":"Q2205967","labels":{"en":{"language":"en","value":"From NP-completeness to DP-completeness: a membrane computing perspective"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7263676"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$9031A73D-4FD5-42F2-98A9-B85B04E8EEDE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4d14b1ca1b68612430d90075d9c61a56dfa1bd8","datavalue":{"value":{"text":"From NP-completeness to DP-completeness: a membrane computing perspective","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2205967$2160A628-4ADE-403F-813A-A8F3357BDEFE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68cd204454d3748ed98b259067d2b741f2275d7e","datavalue":{"value":"1445.68094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205967$4884D6CF-136A-4FF3-9DAB-E9DF365757A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"04d83ccbd9774ee33a1d5df28830d1b61268c04e","datavalue":{"value":"10.1155/2020/6765097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205967$D47B5DCC-A5C1-4A44-9150-0AC42A7353C9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b91360437b6c70ddae4fecbb0aaf01a02c120dc6","datavalue":{"value":{"entity-type":"item","numeric-id":264550,"id":"Q264550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$50969D12-CC32-42A3-B760-8C95B43558B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"124c17c00fc9a824a5ad42776e33d6cfdea37fc4","datavalue":{"value":{"entity-type":"item","numeric-id":1643129,"id":"Q1643129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$55AAA3E8-0D73-4B10-8075-023808B5CD0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f27e8b75af58365328bd15a39e748e2557208796","datavalue":{"value":{"entity-type":"item","numeric-id":537823,"id":"Q537823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$12D1CCFB-A16B-4D96-B844-A512D5822604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"625f2394ea426465cf0fa2a72da08c2a94a03f39","datavalue":{"value":{"entity-type":"item","numeric-id":243843,"id":"Q243843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$EC21CBF5-54BD-488A-BCD7-8A3B0C07F482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d2a1e20b510bc3bc16fa3a132887ba22d27d98c","datavalue":{"value":{"entity-type":"item","numeric-id":987961,"id":"Q987961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$94E0779B-C240-4694-BDB6-FCFC10C10425","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1dec05d6eca21826ddc25d78a5bfbbb3575f964c","datavalue":{"value":{"entity-type":"item","numeric-id":86231,"id":"Q86231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$1E26A761-894C-45C9-8307-2E113CE041AE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"748d3dc0e1ee905f3f3c3b9e1892866fd8648815","datavalue":{"value":{"time":"+2020-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2205967$CDCE8AF0-03E1-4579-AF1A-9759018BBF2D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"231ecba0a9345dfbb9708cef88613cdb9b6707ec","datavalue":{"value":"Summary: \\textit{Presumably efficient} computing models are characterized by their capability to provide polynomial-time solutions for \\(\\mathbf{NP}\\)-complete problems. Given a class \\(\\mathcal{R}\\) of recognizer membrane systems, \\(\\mathcal{R}\\) denotes the set of decision problems solvable by families from \\(\\mathcal{R}\\) in polynomial time and in a uniform way. \\(\\mathbf{PMC}_{\\mathcal{R}}\\) is closed under complement and under polynomial-time reduction. Therefore, if \\(\\mathcal{R}\\) is a presumably efficient computing model of recognizer membrane systems, then \\(\\textbf{NP} \\cup \\textbf{co-NP} \\subseteq \\textbf{PMC}_{\\mathcal{R}}\\). In this paper, the lower bound \\(\\textbf{NP} \\cup \\textbf{co-NP}\\) for the time complexity class \\(\\mathbf{PMC}_{\\mathcal{R}}\\) is improved for any presumably efficient computing model \\(\\mathcal{R}\\) of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that \\(\\textbf{DP} \\cup \\textbf{co-DP}\\) is a lower bound for such \\(\\mathbf{PMC}_{\\mathcal{R}}\\), where \\(\\mathbf{DP}\\) is the class of differences of any two languages in \\(\\mathbf{NP}\\). Since \\(\\textbf{NP} \\cup \\textbf{co-NP} \\subseteq \\textbf{DP} \\cap \\textbf{co-DP}\\), this lower bound for \\(\\mathbf{PMC}_{\\mathcal{R}}\\) delimits a thinner frontier than that with \\(\\textbf{NP} \\cup \\textbf{co-NP}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2205967$1F7F4876-37D0-4684-8EAA-51A6F7184772","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"08d6627ae2c019bef2c123de72ca8195cdbf2423","datavalue":{"value":"68Q07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205967$EA27B26E-4CC4-4FC8-B6F9-B7693B1AEE27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205967$C7D8B0DC-650E-4D4C-B6F0-8A834A905A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205967$1310A7A1-3A83-4F4F-AC02-FC612F8B4978","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c312213116ec0fa8bf269edd5db62665cf12bf07","datavalue":{"value":"7263676","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205967$8CF316BD-5315-465E-AD81-57C5F05048D1","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$D75307DB-16DC-4EA2-9FEE-F86B7564DCB7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"196564a12bf1b84d95dc61c223096e80a9b7b464","datavalue":{"value":"https://doi.org/10.1155/2020/6765097","type":"string"},"datatype":"url"},"type":"statement","id":"Q2205967$69CF67C6-4AA9-473A-B23C-97E374F2D4E4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3bb84725b3f50b67373387da27ca41807fe1f740","datavalue":{"value":"W3081647592","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2205967$58EE69ED-595C-4BB7-8296-75B1F0B76BDB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cd886bfabf37bdc38051593779553a53009e866","datavalue":{"value":{"entity-type":"item","numeric-id":4413842,"id":"Q4413842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$F4ECEBF3-CEEB-4700-AE97-DA83F27E229C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6756f38c1a6c7aea827aa064c75d43ff1eaee43","datavalue":{"value":{"entity-type":"item","numeric-id":1410766,"id":"Q1410766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$3D39CEB4-8FE2-46F5-9EE4-81C0F074BFD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b3dc73388e37abea4d74e9742cae5b5e3ec3afc","datavalue":{"value":{"entity-type":"item","numeric-id":896708,"id":"Q896708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$9BFA2B7B-B9C4-4D0A-AAB6-00D738CFB514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec1283408cdd04549373baa7949bd38245d2d32","datavalue":{"value":{"entity-type":"item","numeric-id":2707525,"id":"Q2707525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$7FB228C1-4DB0-4F61-AC6B-3654EFEA1925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68656fe86e0e898cc6183979289c126f2ca7e7cb","datavalue":{"value":{"entity-type":"item","numeric-id":5897728,"id":"Q5897728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$1BC8E427-5F91-4824-BDFC-F9BC11B85BAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea943e6c76c5422993db263555162d414a4707aa","datavalue":{"value":{"entity-type":"item","numeric-id":2306012,"id":"Q2306012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$1D0BC675-9C26-4392-99DA-70474E0C61A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"641c4e5a970820551ddf1324567d3983f231d26a","datavalue":{"value":{"entity-type":"item","numeric-id":5114220,"id":"Q5114220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$D3FEFA7A-84A6-4F03-9971-5209AA95B7C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbb9ed606faf06214b88e6d857189bfcca5f8cb4","datavalue":{"value":{"entity-type":"item","numeric-id":2216105,"id":"Q2216105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$D91E84EB-93D2-4C2D-BB88-0A88278581FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$0D302DC5-BE96-4F13-98D8-4798BED9B117","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$CD2CE3AD-35A6-4B62-A78B-765A8CE980E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$5F033BF7-8A5A-4FD6-B7CC-04021E04665B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$DA71538B-D906-44A9-B669-4D50108A7E95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f83662ae316121ea72100b37e1d7f310700b0f0a","datavalue":{"value":{"entity-type":"item","numeric-id":3703297,"id":"Q3703297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$F22957EB-A3BB-4922-BA56-CCC3A7404A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bcb11f0b30802ff1fa8b04ab34822dc12429034","datavalue":{"value":{"entity-type":"item","numeric-id":3832042,"id":"Q3832042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$4E568F79-8F3E-4220-A4BD-17F2D4DB54D9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"151dc95d88f9ba843ed097239b3975f3f3c7ee04","datavalue":{"value":{"entity-type":"item","numeric-id":5316643,"id":"Q5316643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca476bfeb661b9e24381434654b00b891a33c3a4","datavalue":{"value":{"amount":"+0.8267291188240051","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2205967$78D96291-D84C-4961-92F2-378F5B56F94A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8ec05ad915402d97c684c89794839145fbb6b17","datavalue":{"value":{"entity-type":"item","numeric-id":1410766,"id":"Q1410766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3774fbbf145b52edc187a4d74b595b5f7883dd10","datavalue":{"value":{"amount":"+0.8230436444282532","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2205967$3CE38904-A41F-4681-890D-2138115D5C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b647a20f8ce0f135aa07896a1f6f051d38a2b3e2","datavalue":{"value":{"entity-type":"item","numeric-id":2299891,"id":"Q2299891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"322353213e734be79b7f95e04c610c593a554855","datavalue":{"value":{"amount":"+0.7990962266921997","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2205967$CF5CD564-1987-4AE4-B13F-BA07296EF4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"759b86c9e0ea751704f031a5e00c0e17dca34f73","datavalue":{"value":{"entity-type":"item","numeric-id":5901846,"id":"Q5901846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cc9a9d3a5a537aa4eb2ea0ff13e9f8f11cb6457","datavalue":{"value":{"amount":"+0.7898374795913696","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2205967$9262486A-AE12-4843-AD20-9EB6FE990EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88697524a10b8246ac53a81e756a9b1902504448","datavalue":{"value":{"entity-type":"item","numeric-id":5851902,"id":"Q5851902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50c3a567e3107cb291d932e1953a4ad1ea2b5d9c","datavalue":{"value":{"amount":"+0.788886547088623","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2205967$E1BD9DB2-905C-4A38-BA30-1D40DAC2BEDE","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2205967$1CDB4CB3-7575-4840-AC8C-FF17F0AC543A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"From NP-completeness to DP-completeness: a membrane computing perspective","badges":[]}}}}}