From NP-completeness to DP-completeness: a membrane computing perspective

DOI10.1155/2020/6765097zbMath1445.68094OpenAlexW3081647592MaRDI QIDQ2205967

Ignacio Pérez-Hurtado, Luis Valencia-Cabrera, David Orellana-Martín, Mario J. Pérez-Jiménez, Miguel A. Martínez-del-Amor

Publication date: 21 October 2020

Published in: Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1155/2020/6765097

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Related Items (1)

From \texttt{SAT} to \texttt{SAT}-\texttt{UNSAT} using P systems with dissolution rules

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Membrane fission versus cell division: when membrane proliferation is not enough
• The polynomial-time hierarchy
• Complexity classes in models of cellular computing with membranes
• Cell-like P systems with evolutional symport/antiport rules and membrane creation
• Cell-like P systems with polarizations and minimal rules
• The Boolean Hierarchy I: Structural Properties
• Membrane Creation in Polarizationless P Systems with Active Membranes
• Membrane Computing

This page was built for publication: From NP-completeness to DP-completeness: a membrane computing perspective