From NP-Completeness to DP-Completeness: A Membrane Computing Perspective
作者： Luis Valencia-Cabrera , David Orellana-Martín , Miguel Á. Martínez-del-Amor , Ignacio Pérez-Hurtado , Mario J. Pérez-Jiménez
DOI: 10.1155/2020/6765097
关键词: Upper and lower bounds 、 Combinatorics 、 Completeness (order theory) 、 Membrane computing 、 Time complexity 、 Reduction (recursion theory) 、 Mathematics
摘要: 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 decision problems solvable families from in polynomial time and uniform way. is closed under complement reduction. Therefore, if presumably model then   co - . In this paper, lower bound complexity improved any systems verifying some simple requirements. Specifically, it shown that DP such , where differences two languages Since delimits thinner frontier than with
hindawi.com
us.es
philpapers.org参考文章(7)
Luis F. Macías-Ramos, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, Luis Valencia-Cabrera, Membrane fission versus cell division Theoretical Computer Science. ,vol. 608, pp. 57- 65 ,(2015) , 10.1016/J.TCS.2015.06.025
Mario J. Péerez Jiménez, Álvaro Romero Jiménez, Fernando Sancho Caparrini, Complexity classes in models of cellular computing with membranes Natural Computing. ,vol. 2, pp. 265- 285 ,(2003) , 10.1023/A:1025449224520
Larry J. Stockmeyer, The polynomial-time hierarchy☆ Theoretical Computer Science. ,vol. 3, pp. 1- 22 ,(1976) , 10.1016/0304-3975(76)90061-X
Jin-Yi Cai, Thomas Gundermann, Juris Hartmanis, Lane A. Hemachandra, Vivian Sewelson, Klaus Wagner, Gerd Wechsung, The Boolean hierarchy I: structural properties SIAM Journal on Computing. ,vol. 17, pp. 1232- 1252 ,(1988) , 10.1137/0217078
Linqiang Pan, David Orellana-Martín, Bosheng Song, Mario J. Pérez-Jiménez, Cell-like P systems with polarizations and minimal rules Theoretical Computer Science. ,vol. 816, pp. 1- 18 ,(2020) , 10.1016/J.TCS.2019.10.001
David Orellana-Martín, Luis Valencia-Cabrera, Agustín Riscos-Núñez, Mario J. Pérez-Jiménez, Membrane Creation in Polarizationless P Systems with Active Membranes Fundamenta Informaticae. ,vol. 171, pp. 297- 311 ,(2019) , 10.3233/FI-2020-1884
Bosheng Song, Kenli Li, David Orellana-Martín, Luis Valencia-Cabrera, Mario J. Pérez-Jiménez, Cell-like P systems with evolutional symport/antiport rules and membrane creation Information & Computation. ,vol. 275, pp. 104542- ,(2020) , 10.1016/J.IC.2020.104542