From NP-completeness to DP-completeness: a membrane computing perspective (Q2205967)

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}\).